슬라이딩 윈도우 (Sliding Window)

관련 문제

문제	난이도	핵심
연속 부분 수열 합의 개수	Lv.2	슬라이딩 윈도우 기본
최소창	Lv.3	가변 윈도우
광고 삽입	Lv.3	슬라이딩 윈도우 응용

---

1. 개념

슬라이딩 윈도우는 고정된 또는 가변적인 구간을 오른쪽으로 이동하면서 탐색하는 방식이다.

브루트포스로 O(N²)이 걸리는 구간 합/최댓값 문제를 O(N)으로 줄일 수 있다.

크기 3인 윈도우로 최대 합 구하기

[1, 2, 3, 4, 5]
 ------           1+2+3 = 6
    ------        2+3+4 = 9
       ------     3+4+5 = 12 ✅

매번 처음부터 다시 더하는 게 아니라, 윈도우가 오른쪽으로 이동할 때 왼쪽 값을 빼고 오른쪽 값을 더하는 방식으로 O(1)에 갱신한다.

---

2. 동작 과정

[1, 2, 3, 4, 5] 에서 크기 3인 윈도우의 최대 합

단계	윈도우	합	동작
초기	[1, 2, 3]	6	첫 윈도우 합 계산
1	[2, 3, 4]	9	-1 +4
2	[3, 4, 5]	12	-2 +5 → 최대 ✅

---

3. 핵심 사용 패턴

고정 크기 윈도우

윈도우 크기가 고정된 경우다.

1. 첫 번째 윈도우의 합/값을 계산
2. 윈도우를 오른쪽으로 한 칸씩 이동
3. 이동할 때마다 왼쪽 값 제거, 오른쪽 값 추가
4. 최대/최소값 갱신

가변 크기 윈도우

조건을 만족하는 최소/최대 구간을 찾는 경우다.

left = 0, right = 0

right를 늘리면서 조건 만족 여부 확인
조건 초과하면 left를 늘려서 윈도우 축소
조건 만족하면 결과 갱신

---

4. 핵심 포인트 2가지

투 포인터와의 차이

	슬라이딩 윈도우	투 포인터
이동 방향	같은 방향 (→)	양 끝에서 좁혀옴
목적	연속 구간의 합/최댓값	두 원소의 관계 탐색
정렬 필요	불필요	대부분 필요
윈도우 크기	고정 또는 가변	가변

구간 합은 미리 계산해두면 빠르다

구간 합을 반복해서 구해야 하는 경우 누적 합(Prefix Sum) 을 미리 계산해두면 O(1)에 구간 합을 구할 수 있다.

prefix[i] = arr[0] + arr[1] + ... + arr[i]
구간 [l, r] 합 = prefix[r] - prefix[l-1]

---

5. 시간복잡도

유형	시간복잡도	비고
브루트포스 구간 합	O(N²)	매번 처음부터 계산
슬라이딩 윈도우	O(N)	한 번 순회
누적 합 + 슬라이딩 윈도우	O(N)	전처리 O(N) + 탐색 O(N)

---

6. 주의사항

• 정렬이 필요 없다. 슬라이딩 윈도우는 연속 구간을 다루기 때문에 정렬하면 오히려 의미가 없어진다.
• 고정 크기인지 가변 크기인지 먼저 파악해라. 패턴이 달라지기 때문에 문제를 잘 읽어야 한다.
• 왼쪽 값 제거를 빠뜨리지 마라. 윈도우를 이동할 때 오른쪽 값 추가만 하고 왼쪽 값 제거를 빠뜨리면 틀린다.
• 투 포인터와 혼동하지 마라. 연속 구간이면 슬라이딩 윈도우, 두 원소의 관계면 투 포인터다.