빠른 비교
| 형태 | 구간 크기 | 움직임 | 대표 문제 |
|---|---|---|---|
| 고정 윈도우 | 일정 | 더하고 빼며 이동 | 길이 k 최대 합 |
| 가변 윈도우 | 조건에 따라 변함 | 오른쪽 확장, 왼쪽 축소 | 합 제한, 중복 없는 부분 문자열 |
| prefix sum | 직접 이동 없음 | 누적합 차이 | 여러 구간 합 질의 |
고정 길이
고정 길이 윈도우는 처음 k개 합을 구한 뒤, 오른쪽 값을 더하고 왼쪽 값을 빼며 이동합니다.
csharp
int sum = 0;
for (int i = 0; i < k; i++)
{
sum += arr[i];
}
int best = sum;
for (int right = k; right < arr.Length; right++)
{
sum += arr[right];
sum -= arr[right - k];
best = Math.Max(best, sum);
}매 구간을 새로 합산하면 O(nk)이지만, 이전 구간의 합을 재사용하면 O(n)이 됩니다.
가변 길이
가변 윈도우는 오른쪽 포인터로 구간을 넓히고, 조건이 깨지면 왼쪽 포인터를 움직여 다시 조건을 맞춥니다.
csharp
int left = 0;
int sum = 0;
for (int right = 0; right < arr.Length; right++)
{
sum += arr[right];
while (sum > limit)
{
sum -= arr[left];
left++;
}
best = Math.Max(best, right - left + 1);
}이 방식은 구간 조건이 포인터 이동에 따라 단조적으로 조절될 때 잘 맞습니다.
선택 기준
| 문제 신호 | 판단 |
|---|---|
| 연속된 k개 | 고정 슬라이딩 윈도우 |
| 연속 구간 합이 조건을 만족 | 가변 윈도우 |
| 구간 합 질의가 여러 번 | prefix sum |
| 음수가 섞인 합 조건 | 슬라이딩 윈도우 전제 재검토 |
| 중복 없는 문자열 | 빈도 맵 + 윈도우 |
음수가 없는 배열의 합 조건은 오른쪽을 늘리면 합이 커지고, 왼쪽을 줄이면 합이 작아지는 단조성이 있습니다. 음수가 섞이면 이 단조성이 깨질 수 있습니다.
주의할 점
슬라이딩 윈도우는 “연속 구간” 문제에 쓰는 패턴입니다. 부분수열처럼 원소를 건너뛸 수 있는 문제에는 맞지 않습니다.
또 가변 윈도우에서 조건을 만족한 뒤 답을 갱신할지, 조건을 깨기 직전에 갱신할지 문제 요구에 따라 달라집니다. 최대 길이와 최소 길이 문제의 갱신 위치를 구분하세요.