Quick Comparison
고정 길이는 들어오는 값과 나가는 값만 바꾸면 됩니다. 가변 길이는 왼쪽을 줄여도 조건이 한 방향으로 회복되는 단조성이 있어야 하며, 합 조건에서는 보통 원소가 음수가 아니어야 합니다.
| 형태 | 구간 크기 | 움직임 | 대표 문제 |
|---|---|---|---|
| 고정 윈도우 | 일정 | 더하고 빼며 이동 | 길이 k 최대 합 |
| 가변 윈도우 | 조건에 따라 변함 | 오른쪽 확장, 왼쪽 축소 | 합 제한, 중복 없는 부분 문자열 |
| 누적합 | 직접 이동 없음 | 누적합 차이 | 여러 구간 합 질의 |
고정 길이
고정 길이 윈도우는 처음 k개 합을 구한 뒤, 오른쪽 값을 더하고 왼쪽 값을 빼며 이동합니다.
csharp
static long MaxFixedWindowSum(IReadOnlyList<int> values, int k)
{
if (k <= 0 || k > values.Count)
{
throw new ArgumentOutOfRangeException(nameof(k));
}
long sum = 0;
for (int i = 0; i < k; i++) sum += values[i];
long best = sum;
for (int right = k; right < values.Count; right++)
{
sum += values[right];
sum -= values[right - k];
best = Math.Max(best, sum);
}
return best;
}k == 0이나 k > values.Count에서 무엇을 답으로 볼지는 문제마다 다릅니다. 위 함수는 길이가 정확히 k인 비어 있지 않은 구간만 받도록 입력 오류로 처리합니다. 매 구간을 새로 합산하면 O(nk)이지만, 이전 구간의 합을 재사용하면 O(n)이 됩니다.
가변 길이
가변 윈도우는 오른쪽 포인터로 구간을 넓히고, 조건이 깨지면 왼쪽 포인터를 움직여 다시 조건을 맞춥니다.
csharp
static int LongestSumAtMost(IReadOnlyList<int> values, long limit)
{
if (limit < 0) throw new ArgumentOutOfRangeException(nameof(limit));
int left = 0;
long sum = 0;
int best = 0;
for (int right = 0; right < values.Count; right++)
{
if (values[right] < 0)
{
throw new ArgumentException("음수 원소는 이 전제를 깨뜨립니다.", nameof(values));
}
sum += values[right];
while (sum > limit)
{
sum -= values[left++];
}
best = Math.Max(best, right - left + 1);
}
return best;
}이 함수는 빈 배열에 0을 반환합니다. 이 방식은 구간 조건이 포인터 이동에 따라 단조적으로 조절될 때 잘 맞습니다. 최소 길이를 찾는 문제는 조건을 만족하는 동안 길이를 갱신한 뒤 왼쪽을 줄여야 하므로 갱신 위치가 반대입니다.
선택 기준
| 문제 신호 | 판단 |
|---|---|
| 연속된 k개 | 고정 슬라이딩 윈도우 |
| 연속 구간 합이 조건을 만족 | 가변 윈도우 |
| 구간 합 질의가 여러 번 | prefix sum |
| 음수가 섞인 합 조건 | 슬라이딩 윈도우 전제 재검토 |
| 중복 없는 문자열 | 빈도 맵 + 윈도우 |
음수가 없는 배열의 합 조건은 오른쪽을 늘리면 합이 커지고, 왼쪽을 줄이면 합이 작아지는 단조성이 있습니다. 음수가 섞이면 이 단조성이 깨질 수 있습니다.
주의할 점
슬라이딩 윈도우는 “연속 구간” 문제에 쓰는 패턴입니다. 부분수열처럼 원소를 건너뛸 수 있는 문제에는 맞지 않습니다.
또 가변 윈도우에서 조건을 만족한 뒤 답을 갱신할지, 조건을 깨기 직전에 갱신할지 문제 요구에 따라 달라집니다. 최대 길이와 최소 길이 문제의 갱신 위치를 구분하세요.
참고 링크
1 sources