슬라이딩 윈도우

🎯 학습 목표

이 강을 마치면 슬라이딩 윈도우로 구간 문제를 O(n)에 푸는 표준 틀을 갖게 됩니다. 고정 크기 창과 가변 크기 창을 구분하고, 창 안의 상태(합·개수·최댓값)를 버리고 더하는 방식으로 갱신하는 패턴을 익힙니다.

11강 투 포인터 형태 2를 특화한 기법이라 겹치는 부분이 있습니다. 이 강에서는 "창 안의 상태를 어떻게 관리하는가"에 초점을 맞춥니다. 상태 관리를 잘못하면 O(n)이 될 것이 O(n²)가 됩니다.

💡 다시 계산하지 말고 갱신하라

슬라이딩 윈도우의 아이디어는 하나입니다. 창이 한 칸 옮겨 갈 때 대부분의 원소는 그대로 남아 있으므로, 나간 것만 빼고 들어온 것만 더한다는 것입니다.

고정 크기 3인 창의 합

  [1, 4, 2, 10, 2, 3]

  창 [1,4,2]        합 7
       ↓ 한 칸 이동
  창 [4,2,10]       합 = 7 - 1 + 10 = 16
       ↓
  창 [2,10,2]       합 = 16 - 4 + 2 = 14
       ↓
  창 [10,2,3]       합 = 14 - 2 + 3 = 15

  ▲ 매번 sum() 을 부르면
    창 크기 k × 창 개수 n → O(n × k)

  ▲ 나간 것만 빼고 들어온 것만 더하면
    이동 한 번에 O(1) × n번 → O(n)

  ▲ 핵심 등식
    새 합 = 이전 합 - 나가는 원소 + 들어오는 원소

  가변 크기 창 (조건을 만족하도록 크기가 변함)

  "중복 없는 가장 긴 부분문자열"  "abcabcbb"

   창                상태(등장한 글자)   동작
   a                 {a}                늘린다
   ab                {a,b}              늘린다
   abc               {a,b,c}            늘린다 · 길이 3 기록
   abca              a 중복!            → 왼쪽을 a 다음까지 줄인다
   bca               {b,c,a}            늘린다
   ...

  ▲ 오른쪽은 계속 전진, 왼쪽은 조건이 깨질 때만 전진
    둘 다 되돌아가지 않으므로 O(n)

📖 상태 관리가 전부다

슬라이딩 윈도우 문제는 "창 안의 무엇을 알아야 하는가"에 따라 필요한 자료구조가 달라집니다. 여기가 난이도를 결정합니다.

알아야 하는 것	자료구조	갱신 비용
합	변수 하나	O(1)
개수·빈도	딕셔너리 / Counter	평균 O(1)
중복 여부	집합 또는 딕셔너리	평균 O(1)
최댓값·최솟값	덱(단조 덱)	상각 O(1)
정렬된 상태	힙 또는 균형 트리	O(log k)

여기서 최댓값이 까다롭습니다. 창에서 원소가 하나 빠질 때, 그 원소가 최댓값이었다면 새 최댓값을 다시 찾아야 하기 때문입니다. 매번 max()를 부르면 O(k)가 들어 전체가 O(n × k)가 됩니다.

해법이 6강에서 본 단조 덱입니다.

단조 덱이 최댓값을 O(1)로 유지하는 원리

  덱에는 '인덱스'를 담고, 값이 내림차순이 되도록 유지한다

  새 값 num 이 들어올 때
   ① 창을 벗어난 인덱스를 왼쪽에서 버린다
   ② 덱 뒤쪽에 num 보다 작은 값들이 있으면 전부 버린다
      → 이유: num 이 더 크고 더 늦게 들어왔으므로
        그 값들은 앞으로 절대 최댓값이 될 수 없다
   ③ num 의 인덱스를 뒤에 넣는다
   → 덱의 맨 앞이 항상 창의 최댓값

  [1, 3, -1, -3, 5]  창 크기 3

   i=0 num=1   덱 [0]           (값 1)
   i=1 num=3   1<3 버림 → 덱 [1]  (값 3)
   i=2 num=-1  덱 [1,2]        (3, -1) → 창 최댓값 3
   i=3 num=-3  덱 [1,2,3]      → 최댓값 3
   i=4 num=5   창 벗어난 1 버림, -1·-3 버림 → 덱 [4] → 최댓값 5

  ▲ 각 인덱스는 한 번 들어가고 최대 한 번 나온다
    → 전체 상각 O(n)

💻 실전 예제 — 고정 창과 가변 창

from collections import defaultdict


def max_sum_fixed(nums, k):
    """크기 k 구간의 최대 합 → O(n)"""
    window = sum(nums[:k])           # 첫 창은 한 번만 계산
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # 들어온 것 - 나간 것
        best = max(best, window)
    return best


def longest_unique(s):
    """중복 없는 가장 긴 부분문자열 길이 → O(n)"""
    last_seen = {}                   # 글자 → 마지막 등장 인덱스
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1      # 중복 글자 다음으로 점프
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best


def count_anagram_positions(s, p):
    """s 안에서 p 의 애너그램이 시작하는 위치 개수 → O(n)"""
    if len(p) > len(s):
        return 0
    need = defaultdict(int)
    for ch in p:
        need[ch] += 1
    window = defaultdict(int)
    count = 0
    for i, ch in enumerate(s):
        window[ch] += 1                       # 들어온 글자
        if i >= len(p):
            out = s[i - len(p)]
            window[out] -= 1                  # 나간 글자
            if window[out] == 0:
                del window[out]               # 0은 지워야 비교가 맞다
        if window == need:
            count += 1
    return count


print(max_sum_fixed([1, 4, 2, 10, 2, 3], 3))       # 16
print(longest_unique("abcabcbb"))                   # 3
print(count_anagram_positions("cbaebabacd", "abc")) # 2

코드를 줄 단위로 보겠습니다.

• window = sum(nums[:k]) — 첫 창만 직접 계산합니다. O(k)이고 한 번만 합니다.
• window += nums[i] - nums[i - k] — 핵심 한 줄입니다. 들어온 원소를 더하고 나간 원소를 뺍니다. i - k가 창에서 빠지는 인덱스입니다.
• if ch in last_seen and last_seen[ch] >= left — 두 조건이 모두 필요합니다. 본 적이 있어도 그 위치가 이미 창 밖이면 중복이 아닙니다. 이 조건을 빠뜨리면 창이 잘못 줄어듭니다.
• left = last_seen[ch] + 1 — 한 칸씩 줄이지 않고 바로 점프합니다. 그래도 left는 되돌아가지 않으므로 O(n)이 유지됩니다.
• if window[out] == 0: del window[out] — 딕셔너리 비교에서 값이 0인 키가 남아 있으면 need와 다르다고 판정됩니다. 반드시 지워야 합니다. 이것이 이 문제의 대표적인 함정입니다.
• if window == need — 딕셔너리끼리 내용 비교입니다. 알파벳 종류가 상수 개(최대 26개 등)이므로 비교 비용도 사실상 상수로 볼 수 있습니다.

세 함수 모두 각 원소가 창에 한 번 들어오고 한 번 나가므로 전체가 O(n)입니다.

⚠️ 자주 하는 실수

첫째, 창 안을 매번 다시 계산합니다. sum(nums[i:i+k])나 max(window)를 반복문 안에서 부르면 슬라이딩 윈도우를 쓰는 의미가 사라집니다. 반드시 갱신 방식으로 쓰세요.

둘째, 빈도 딕셔너리에서 0을 안 지웁니다. 위 예제의 함정입니다. window[out] -= 1 후 0이면 키를 삭제해야 비교가 정확합니다.

셋째, left가 되돌아가게 만듭니다. 가변 창에서 left를 줄이는 코드를 쓰면 O(n) 보장이 깨집니다. left는 전진만 해야 합니다.

넷째, 창 크기가 배열보다 클 때를 처리하지 않습니다. k > len(nums)면 첫 창을 만들 수 없어 오류가 납니다. 입력 검증을 앞에 두세요.

다섯째, 고정 창인데 가변 창처럼 짭니다. 크기가 정해져 있으면 while로 줄일 필요가 없습니다. 단순한 for 하나로 끝납니다. 문제를 읽을 때 "창 크기가 고정인가"부터 확인하세요.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	다시 계산하지 말고 갱신한다
2	새 합 = 이전 합 - 나간 것 + 들어온 것
3	고정 창은 for 하나, 가변 창은 while 추가
4	상태에 따라 자료구조가 달라진다
5	최댓값 유지는 단조 덱
6	빈도 딕셔너리는 0을 삭제
7	left는 전진만

지금 해 볼 것은 count_anagram_positions에서 del window[out] 줄을 지우고 실행해 보는 것입니다. 답이 0으로 나오는 것을 보면 왜 0을 지워야 하는지 확실해집니다.

다음 13강 「재귀」부터는 새로운 축으로 넘어갑니다. 함수가 자기 자신을 부르는 구조를 다루고, 9강 병합 정렬에서 잠깐 쓴 기저 조건을 제대로 정리합니다. 그리고 재귀가 내부적으로 스택으로 동작한다는 사실을 5강과 연결하겠습니다.

📚 참고 자료

• collections.deque — Python 공식 문서
• collections.defaultdict — Python 공식 문서
• TimeComplexity — Python Wiki