21. 슬라이딩 윈도우

슬라이딩 윈도우

빠른 설명

슬라이딩 윈도우는 연속 구간을 유지하면서 한 칸씩 이동하는 기법이다. 이전 구간의 계산 결과를 재사용하므로 매번 구간 전체를 다시 계산하지 않는다.

언제 쓰는가

• 길이가 고정된 연속 구간의 최댓값/최솟값/합
• 조건을 만족하는 가장 긴 또는 가장 짧은 연속 구간
• 배열, 문자열에서 연속 부분을 다룰 때

시간복잡도

• 보통 $O(N)$

참고자료

• USACO Guide - Two Pointers and Sliding Window
• GeeksforGeeks - Sliding Window Technique
• CodePath - Two Pointer / Sliding Window

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    vector<int> a = {1, 3, 2, 6, 4, 2};
    int k = 3;
 
    int window_sum = 0;
    for (int i = 0; i < k; i++) window_sum += a[i];
 
    int best = window_sum;
    for (int i = k; i < (int)a.size(); i++) {
        window_sum += a[i];
        window_sum -= a[i - k];
        best = max(best, window_sum);
    }
 
    cout << best << '\n';
}

Python 코드

a = [1, 3, 2, 6, 4, 2]
k = 3
 
window_sum = sum(a[:k])
best = window_sum
 
for i in range(k, len(a)):
    window_sum += a[i]
    window_sum -= a[i - k]
    best = max(best, window_sum)
 
print(best)