슬라이딩 윈도우란?
슬라이딩 윈도우(Sliding Window)는 연속된 구간(윈도우)을 배열 위에서 한 칸씩 미끄러뜨리며, 구간 합·최댓값 같은 값을 O(n)에 유지하는 기법입니다. 매번 구간을 처음부터 다시 계산하면 O(nk)인데, 들어오는 값은 더하고 나가는 값은 빼서 갱신하면 O(n)으로 줄어듭니다.
핵심 한 줄: "겹치는 부분을 다시 계산하지 마라." 한 칸 이동해도 구간의 대부분은 그대로입니다.
두 종류의 윈도우
- •고정 크기 윈도우: 크기
k가 정해져 있고, 한 칸씩 오른쪽으로 밉니다. "연속 k개의 최대 합" 같은 문제. - •가변 크기 윈도우: 조건을 만족할 때까지 오른쪽 끝을 넓히고, 조건이 깨지면 왼쪽 끝을 줄입니다(투 포인터의 같은 방향 버전). "합이 target 이상인 최소 길이" 같은 문제.
동작 원리 (고정 크기)
1단계. 처음 k개의 합을 먼저 계산합니다.
2단계. 윈도우를 오른쪽으로 한 칸 밀 때, 합 += arr[r] (새로 들어온 값), 합 -= arr[l] (빠져나간 값)으로 갱신합니다.
3단계. 이동할 때마다 최댓값이나 조건을 확인합니다.
가변 윈도우라면, 오른쪽을 계속 넓히다가 조건을 위반하면 while로 왼쪽을 줄여 다시 만족시키며 최적 길이를 추적합니다.
알고노트 시각화는 윈도우가 미끄러질 때 어떤 값이 더해지고 빠지는지 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(n) |
| 공간 | O(1) ~ O(k) |
각 원소가 윈도우에 한 번 들어오고 한 번 나가므로 전체 O(n)입니다.
예시로 따라가기
[2, 1, 5, 1, 3, 2], k = 3의 최대 구간 합:
- •첫 윈도우 [2,1,5] = 8
- •한 칸 → +1 −2 → 7 ([1,5,1])
- •한 칸 → +3 −1 → 9 ([5,1,3]) ← 최대
- •한 칸 → +2 −5 → 6 ([1,3,2])
- •답: 9
자주 하는 실수
- •나가는 값 빼기 누락: 들어온 값만 더하고 빠진 값을 안 빼면 윈도우가 아니라 누적합이 됩니다.
- •가변 윈도우 경계: 왼쪽을 줄일 때
if가 아니라while로 조건을 회복할 때까지 줄여야 합니다. - •빈 윈도우/ k > n: 입력보다 큰 윈도우 등 경계 케이스를 먼저 처리하세요.
알고노트에서 직접 확인하세요
윈도우가 오른쪽으로 미끄러질 때 새 값이 더해지고 옛 값이 빠지며 구간 값이 갱신되는 과정을 알고노트에서 단계별로 확인할 수 있습니다.