알고리즘 - 덱

✅덱(Deque, Double-ended Queue)이란 무엇인가?

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조로, 스택과 큐의 기능을 모두 갖고 있다.
덱 알고리즘은 대부분의 경우 스택이나 큐를 사용하는 알고리즘과 비슷한 형태를 가지고 있지만, 덱의 양쪽에서 데이터를 삽입하거나 삭제할 수 있기 때문에 좀 더 다양한 상황에서 사용할 수 있다.

✅덱의 사용

• 큐나 스택으로는 해결하기 어려운 문제
• 슬라이딩 윈도우 알고리즘: 고정된 크기의 윈도우를 슬라이딩하면서 데이터를 처리하는 알고리즘.
• 이중 우선순위 큐 구현: 가장 작은 값과 가장 큰 값 둘 다를 빠르게 찾아내기 위해 사용된다.

덱 알고리즘을 구현할 때는 Deque 자료구조를 이용하거나, 스택이나 큐를 이용해 직접 구현할 수 있다. 따라서, 자바에서는 Deque 인터페이스와 그를 구현한 LinkedList 클래스를 제공하고 있다.

✅코드예제

ex) 크기가 n인 배열과 k라는 자연수가 주어졌을 때, 크기가 k인 윈도우를 오른쪽으로 한 칸씩 이동시키면서 각 윈도우 내부의 합을 계산하시오.

import java.util.*;

public class SlidingWindow {
    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        Deque<Integer> deque = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            // 현재 윈도우에서 벗어난 값 제거
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // 현재 값이 윈도우에 포함되는 값일 때, 덱에 추가
            while (!deque.isEmpty() && arr[deque.peekLast()] < arr[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // 현재 윈도우에서의 최댓값을 결과에 추가
            if (i >= k - 1) {
                result.add(arr[deque.peekFirst()]);
            }
        }

        System.out.println(result);
    }
}

위 코드에서는 Deque 인터페이스를 구현한 LinkedList 클래스를 사용하여 덱을 구현하였다. 크기가 k인 윈도우에서 최댓값을 구하기 위해서는, 현재 위치에서 k개의 인접한 원소를 묶어서 처리해야 합니다. 이때, Deque를 사용하여 현재 윈도우에 포함되는 값들을 저장하고, 다음 윈도우로 이동할 때 마다 윈도우에서 제외되는 값을 제거하면서 윈도우 내부의 최댓값을 구한다.