[알고리즘] 슬라이딩 윈도우(Sliding Window) 알고리즘과 단조 큐(Monotonic Queue)

슬라이딩 윈도우(Sliding Window) 알고리즘

---

투 포인터의 일종으로 윈도우(Start~End 구간)을 한칸씩 이동하며 문제를 해결하는 알고리즘이다. 슬라이딩 윈도우 알고리즘의 두 포인터는 배열 전체를 최대 한번씩만 이동하기 때문에 시간 복잡도는 O(n)이다.윈도우의 크기는 고정일수도 있고 가변일 수도 있다.  

슬라이딩 윈도우 (고정)

 

• 고정 윈도우(Fixed Window)
  윈도우 크기 K가 고정되어있어 K 크기 만큼의 윈도우를 한칸씩 밀며 탐색을 수행한다. End - Start + 1 = K의 관계가 유지되며 보통 슬라이딩 윈도우 라고 하면 고정 윈도우를 의미한다.
• 가변 윈도우(Variable Window
  조건에 따라 Start와 End가 자유롭게 움직이며 윈도우의 크기가 변할 수 있다. 조건에 만족할 때 까지 end를 늘리고, 만족하면 start를 줄이는 탐색 방식이며 사실상 투 포인터와 동일하다.

 

 

슬라이딩 윈도우(구간) 안에서 최댓값/ 최소값을 빠르게(O(1)) 구해야 하는 경우
-> 단조 큐 사용!

 

윈도우 안에서 최대/최소 값을 구해야 하는 경우가 있다. 이때 단조 큐(Monotonic Queue)를 사용한다면 구간 내 최대/최소값 탐색을 O(1)의 시간에 구할 수 있다.  예를 들어 ‘길이 k인 연속 부분 배열의 최댓값을 모두 구하라’는 문제가 있다고 해보자.

arr = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

 

1. 슬라이딩 윈도우 (기본)

여기서 그냥 투포인터를 활용해 윈도우를 밀면서 그 안에서 최댓값을 구하려면 결국 2중 for문이 되어 시간 복잡도가 O(n * k)이 나온다.

for (i = 0; i <= n - k; i++) {
    int mx = arr[i];
    for (j = i; j < i + k; j++)
        mx = max(mx, arr[j]);
    result.push_back(mx);
}

 

 

2. 슬라이딩 윈도우 + 단조큐

위 문제처럼 윈도우 내의 최대/ 최소값을 구해야 할 때 단조 큐를 사용한다면 윈도우 내 후보만 유지하면서 최댓값/최솟값을 O(1)로 관리하하여 O(n)의 시간 복잡도로 탐색을 끝낼 수 있다.

 

단조 큐(Monotonic Queue)는 새로운 값이 들어올 때 불필요한 값들을 제거하여 후보만 유지하는 자료구조이다. 예를 들어 최대 값을 구해야 한다면 새로운 값이 push될 때 마다 input값 보다 작은 요소들을 pop하면서 가장 큰 값이 front에 위치하게 하는 것이다. 단조큐는 앞 뒤에 추가 삭제가 최적화된 deque로 구현된다. 이때 deque의 원소가 윈도우 사이즈를 초과한다면 맨 앞 요소를 pop한다. 이렇게 deque 안에 윈도우 구간의 원소를 유지하면서 맨 앞(front)이 항상 현재 윈도우의 최댓값이 되는 것이다. 모든 원소들은 덱에 한번 들어오고 한번 나가기 때문에 시간 복잡도는 O(n)이다.

// 최소값 유지 단조 큐
입력: [4, 3, 2, 1]
push 4 → dq=[4], min=4
push 3 → dq=[3], min=3   (4>3 제거)
push 2 → dq=[2], min=2   (3>2 제거)
push 1 → dq=[1], min=1   (2>1 제거)

// 슬라이딩 윈도우 + 단조큐
// nums에서 k구간의 최대값 구하기
vector<int> slidingWindowMax(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;

    for (int i = 0; i < nums.size(); i++) {
        // 윈도우 밖 인덱스 제거
        if (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();

        // 새 원소보다 작은 값 제거
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();

        dq.push_back(i);

        // 윈도우가 완성되면 최댓값 기록
        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }
    return result;
}

단조큐를 윈도우 관점에서 정리하면 ‘윈도우 내 후보만 유지하면서 최댓값/최솟값을 O(1)로 관리하는 특수 deque 활용 기법’이라고 할 수 있다.

1. 불필요한 값 제거
    새 값이 들어올 때, 최대값을 구하는 경우 새 값보다 작은 값들은 뒤에서 제거
    최소값을 구하는 경우 새 값보다 큰 값들은 제거
2. 윈도우 범위 유지
    deque 맨 앞(front) 원소가 윈도우 범위를 벗어나면 pop_front
3. 최댓값/최솟값 보장
    deque 안에는 항상 현재 윈도우 후보만 유지
    맨 앞(front) = 현재 윈도우 최댓값(또는 최솟값)
4. 시간 복잡도 O(N)
    각 원소는 한 번 들어오고 한 번 나감 → 전체 O(N)

 

구분	언제 쓰는가?	사용 이유	원리	시간복잡도
슬라이딩 윈도우	연속된 구간에서 합, 평균, 길이, 조건 만족 여부 등 단순 계산	매번 구간 전체를 새로 계산하지 않고, 이전 구간 계산값 활용	left, right 포인터로 구간 이동, 새로 들어오는 값 + 기존 값 갱신, 나가는 값 제거	O(N)
슬라이딩 윈도우 +단조큐	구간 내 최댓값/최솟값을 빠르게 구해야 할 때	단순 탐색 O(K)을 매번 하면 비효율적 → deque로 후보만 유지	deque에 인덱스 저장, 뒤에서 작은 값 제거 → 맨 앞이 항상 최댓값, 범위 벗어나면 제거	O(N)