슬라이딩 윈도우

슬라이딩 윈도우란?

슬라이딩 윈도우(sliding window) 는 배열 위에서 연속한 구간(창, window) 을
한 칸씩 밀면서, 창 안의 정보(합·개수·최댓값 등)를 처음부터 다시 계산하지 않고
갱신만 하여 \(O(N)\)에 처리하는 기법입니다.

투 포인터의 한 형태로, 특히 "연속 구간"을 다룰 때 강력합니다.

1. 핵심 아이디어: 다시 세지 않는다

길이 \(K\) 창의 합을 매번 처음부터 더하면 \(O(NK)\)입니다. 슬라이딩 윈도우는 창이
한 칸 이동할 때 새로 들어온 원소를 더하고, 빠져나간 원소를 빼는 갱신만 하면
되므로 한 번 이동이 \(O(1)\), 전체 \(O(N)\)입니다.

창이 [a b c] → [b c d]로 이동:
새 합 = 옛 합 - a + d   (단 두 번의 연산!)

이 "증분 갱신"이 슬라이딩 윈도우의 전부입니다.

2. 두 종류: 고정 길이 vs 가변 길이

• 고정 길이 창: 창 크기 \(K\)가 정해짐. "길이 \(K\) 구간의 최대 합" 등.
  창을 한 칸씩 밀며 들어온 것 더하고 나간 것 뺀다.
• 가변 길이 창: 조건을 만족하는 한 창을 늘리고, 어기면 줄인다. "합이 \(S\)
  이하인 가장 긴 구간" 등. 투 포인터의 같은 방향 유형과 동일합니다.

3. 고정 길이 예: 창의 합

length-K 창을 오른쪽으로 밀며:
  들어온 원소 a[r] 더하기
  r >= K 이면 빠진 원소 a[r-K] 빼기
  r >= K-1 이면 현재 창의 합을 기록

매 칸 상수 시간 갱신으로 모든 창의 합을 \(O(N)\)에 얻습니다.

4. 가변 길이 예: 조건 만족 최장 구간

"서로 다른 문자가 \(K\)개 이하인 가장 긴 부분 문자열" 같은 문제입니다.

오른쪽 끝 r을 늘려 창을 확장하며 창 안 정보를 갱신.
조건을 어기면 왼쪽 끝 l을 늘려 다시 만족시킨다.
유효할 때마다 길이(r - l + 1)를 최댓값과 비교.

두 포인터가 앞으로만 가므로 \(O(N)\)입니다.

5. 창 안의 정보를 무엇으로 유지하나

창이 유지하는 정보에 따라 보조 자료구조가 달라집니다.

특히 창의 최댓값을 \(O(N)\)에 유지하는 모노톤 덱이 자주 결합됩니다.

정리

슬라이딩 윈도우는 연속 구간을 한 칸씩 밀며 정보를 증분 갱신해 \(O(N)\)에 처리하는
기법입니다. 고정 길이(합)와 가변 길이(조건 만족 구간) 두 패턴을 익히고, 창 안
정보에 맞는 보조 도구를 고르면 됩니다. 다음 강의에서 코드로 완성합니다.

슬라이딩 윈도우를 코드로

고정 길이와 가변 길이 두 패턴, 그리고 빈도 맵을 쓰는 응용을 구현합니다.

1. 고정 길이 창의 최대 합

long long sum = 0, best = LLONG_MIN;
for (int r = 0; r < n; r++) {
    sum += a[r];                       // 새 원소 추가
    if (r >= k) sum -= a[r - k];       // 빠진 원소 제거
    if (r >= k - 1) best = max(best, sum);  // 창이 완성되면 갱신
}

s, best = 0, float('-inf')
for r in range(n):
    s += a[r]
    if r >= k:
        s -= a[r - k]
    if r >= k - 1:
        best = max(best, s)

핵심은 세 줄: 더하고, (창을 벗어나면) 빼고, (창이 꽉 차면) 기록.

2. 가변 길이: 합이 S 이하인 최장 구간 (양수)

int l = 0, best = 0;
long long sum = 0;
for (int r = 0; r < n; r++) {
    sum += a[r];
    while (sum > S) sum -= a[l++];     // 조건 어기면 왼쪽 축소
    best = max(best, r - l + 1);       // 유효 구간 길이
}

l, best, s = 0, 0, 0
for r in range(n):
    s += a[r]
    while s > S:
        s -= a[l]
        l += 1
    best = max(best, r - l + 1)

3. 빈도 맵 응용: 서로 다른 값 K개 이하 최장 구간

unordered_map<int,int> cnt;
int l = 0, best = 0;
for (int r = 0; r < n; r++) {
    cnt[a[r]]++;                        // 새 값 추가
    while ((int)cnt.size() > K) {       // 종류가 K 초과면 축소
        if (--cnt[a[l]] == 0) cnt.erase(a[l]);
        l++;
    }
    best = max(best, r - l + 1);
}

from collections import defaultdict
cnt = defaultdict(int)
l, best = 0, 0
for r in range(n):
    cnt[a[r]] += 1
    while len(cnt) > K:
        cnt[a[l]] -= 1
        if cnt[a[l]] == 0:
            del cnt[a[l]]
        l += 1
    best = max(best, r - l + 1)

빈도가 0이 된 키를 맵에서 지워야 "서로 다른 값의 수 = 맵의 크기"가 정확히
유지됩니다.

4. 창의 최댓값: 모노톤 덱 결합

고정 길이 창의 최댓값은 모노톤 덱으로 \(O(N)\)에 구합니다(덱 강의에서 다룬 코드).
값이 내림차순인 인덱스를 덱에 유지하고, 맨 앞이 현재 창의 최댓값입니다.

5. 흔한 실수

• 창 완성 시점 — 고정 길이에서 r >= k-1이 되어야 첫 창이 완성됩니다.
  너무 일찍 기록하면 부분 창을 셈.
• 빠지는 인덱스 — 한 칸 밀 때 a[r-k]를 빼야 함. 인덱스 어긋나면 답이 틀림.
• 음수 값에서 가변 창 — 합 기반 가변 창은 양수일 때만 단조. 음수가 있으면
  다른 접근(누적 합 등) 필요.
• 빈도 0 키 미삭제 — len(cnt)가 부정확해져 종류 수 계산이 틀림.
• 파이썬 defaultdict 부작용 — 조회만 했는데 0짜리 키가 생길 수 있음.

6. 패턴 알아보기

• "길이 \(K\) 연속 구간의 합/최대/최소" → 고정 길이 슬라이딩 윈도우.
• "조건을 만족하는 가장 긴/짧은 연속 구간" → 가변 길이.
• "서로 다른 ~가 K개 이하/이상인 구간" → 빈도 맵 + 슬라이딩.
• \(O(NK)\)로 보이는 연속 구간 문제 → 증분 갱신으로 \(O(N)\).

실전에서 슬라이딩 윈도우 문제 알아보기

슬라이딩 윈도우는 투 포인터의 특수형으로, "창이 한 칸 움직일 때 정보를
\(O(1)\)로 고칠 수 있는가" 가 성패를 가릅니다. 그 감별법을 다룹니다.

1. 출제 신호

• "길이 \(K\)인 연속 구간"의 합·최대·종류 수 — 고정 창. 모든 위치에서
  다시 계산하면 \(O(NK)\), 창 갱신이면 \(O(N)\)입니다.
• "조건을 만족하는 가장 긴(짧은) 연속 구간" — 가변 창. "서로 다른 수가
  \(K\)종류 이하" 같은 조건이 단골입니다.
• "모든 위치에서 직전 \(K\)개의 최솟값" — 모노톤 덱이 필요한 상급 신호.
• 핵심 감별: 창이 한 칸 이동할 때 나가는 원소 1개, 들어오는 원소 1개의
  효과만 반영하면 되는 구조인가?
• 최댓값·최솟값처럼 "나간 원소가 답이었으면 재계산이 필요한" 통계는 단순
  변수로 안 되고 카운터 맵이나 모노톤 덱이 필요합니다.

2. 풀이 결정 절차

1. 고정 창인가 가변 창인가 — 길이가 \(K\)로 주어지면 고정, 조건으로
   주어지면 가변.
2. 창이 유지할 자료를 고릅니다 — 합이면 변수 하나, 종류 수면 카운터 맵,
   최솟값이면 모노톤 덱.
3. 확장/수축 시 갱신 코드가 대칭인지 확인합니다 — 넣을 때 한 일을 뺄 때
   정확히 되돌려야 합니다.
4. 답 갱신 위치를 정합니다 — 가변 창은 보통 "조건 위반 시 수축"이 끝난
   직후가 안전한 갱신 지점입니다.

3. 자주 하는 실수

• 종류 수 셀 때 0이 된 키를 지우지 않음. len(counter)로 종류 수를 보는
  코드에서 빈도가 0이 된 키를 남겨 두면 종류 수가 과대평가됩니다.

from collections import defaultdict
cnt = defaultdict(int); l = 0; best = 0
for r, x in enumerate(a):
    cnt[x] += 1                       # 확장
    while len(cnt) > K:               # 조건 위반 → 수축
        cnt[a[l]] -= 1
        if cnt[a[l]] == 0:
            del cnt[a[l]]             # 0이면 반드시 삭제!
        l += 1
    best = max(best, r - l + 1)       # 수축이 끝난 뒤 갱신

• 고정 창 초기화 따로, 이동 따로 짜다 경계 실수. 첫 \(K\)개를 채우는
  루프와 이동 루프의 인덱스가 어긋나기 쉽습니다. "매 스텝: \(r\) 추가 →
  창이 크면 \(l\) 제거" 단일 루프로 통일하면 경계가 사라집니다.
• 모노톤 덱에서 만료 원소 제거 누락. 덱 앞쪽 원소가 창을 벗어났는지
  매 스텝 dq[0] <= r - K로 확인해야 합니다. 인덱스를 저장해야 가능합니다.
• 수축 조건의 while을 if로. 한 칸 줄여서 조건이 회복된다는 보장이
  없습니다. 반드시 while로 회복될 때까지 줄이세요.
• 창 통계 변수와 포인터의 불일치 — sum은 갱신했는데 l을 안 옮기는 류.
  확장/수축을 함수로 묶으면 예방됩니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 것부터 어려운 것 순입니다. 고정 창
합 → 가변 창(종류 수 조건) → 모노톤 덱 순서로 유지할 자료가 점점
복잡해집니다.

문제마다 "창이 유지하는 자료가 무엇인가"를 한 단어(변수/카운터/덱)로
먼저 답하고 코딩하세요. 3문제 이상 풀어 클리어하면 레이팅의
CLASS 보너스에 반영됩니다.