[CS]슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우 : Sliding Window

• 슬라이딩 + 윈도우
  • 슬라이딩 : 미끄러지듯이 이동
  • 윈도우 : 특정 범위(고정)
• 고정된 특정 범위를 미끄러지듯이 이동시키며 탐색하는 방법
• 투 포인터와 유사
  • 투 포인터와 달리, 부분 배열의 길이가 고정이므로, 변수가 2개가 아닌 1개 필요
• 구간의 고정 길이(L)를 한 칸 옮기면 L - 1 칸은 겹친다.
  • 기존 모습 : 🟨🟪🟪🟪🟪🟨🟨
  • 다음 모습 : 🟨🟨🟪🟪🟪🟪🟨
  • 겹침 지점 : 🟨🟪🟥🟥🟥🟪🟨
• 빠지게 된 앞 🟪 와 포함된 뒤 🟪 만 비교하는 효율적인 방식
• 시간 복잡도 : $O(N^2)$의 시간 복잡도를 부분배열을 활용해 줄임
  • 최악(worst): $O(2N)$
  • 시간 복잡도: $O(N)$

슬라이딩 윈도우 예제

[2475][P5] . 최소값 찾기

• 대표적인 슬라이딩 윈도우 문제
• 매번 새로운 창문 안에서의 최소값을 출력해야 하는 문제
• 풀이 과정
  • i = 0 : [ 1(0) ]
  • i = 1 : [ 1(0), 5(1) ]
  • i = 2 : [ 1(0), 5(1), 2(2) ]
  • i = 3 : 1(0) [ 5(1), 2(2), 3(3) ]
    우선순위큐에서 가장 최소값(top)이 1(0) 인데 이는 범위를 벗어났으므로 pop
  • i = 4 : [ 5(1), 2(2), 3(3), 6(4) ]
  • i = 5 : 2(2) [ 5(1), 3(3), 6(4), 2(5) ]
    우선순위큐에서 가장 최소값(top)이 2(2) 인데 이는 범위를 벗어났으므로 pop
  • i = 6 : [ 5(1), 3(3), 6(4), 2(5), 3(6) ]
  • i = 7 : [ 5(1), 3(3), 6(4), 2(5), 3(6), 7(7) ]
  • i = 8 : 2(5) [ 5(1), 3(3), 6(4), 3(6), 7(7), 3(8) ]
    우선순위큐에서 가장 최소값(top)이 2(5) 인데 이는 범위를 벗어났으므로 pop
  • i = 9 : [ 5(1), 3(3), 6(4), 3(6), 7(7), 3(8), 5(9) ]
  • i = 10 : [ 5(1), 3(3), 6(4), 3(6), 7(7), 3(8), 5(9), 2(10) ]
  • i = 11 : [ 5(1), 3(3), 6(4), 3(6), 7(7), 3(8), 5(9), 2(10), 6(11) ]

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>
using namespace std;
struct A {
    int data;
    int pos;
};
struct cmp {
    bool operator()(const A& a, const A& b) {
        return a.data > b.data;
    }
};
int main() {
    /* 입출력 속도 높이기 */
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, L;
    cin >> N >> L;
    vector<int> arr(N);
    for (int i = 0; i < N; ++i)
        cin >> arr[i];
    priority_queue<A, vector<A>, cmp> pq;
    for (int i = 0; i < N; ++i) {
        pq.push({ arr[i], i });
        int pos = pq.top().pos;
        while (pos < i - L + 1) {
            pq.pop();
            pos = pq.top().pos;
        }
        cout << pq.top().data << ' ';
    }
    return 0;
}