Sliding Window

Sliding Window 개념 정리

알고리즘 문제에서 자주 등장하는 기법 중 하나가 Sliding Window이다. 처음 들으면 복잡해 보이지만, 사실은 연속된 구간을 효율적으로 탐색하기 위한 방법이다.

1. 문제 상황

예를 들어, 길이가 6인 배열에서 연속된 4개의 원소 합 중 최댓값을 구한다고 하자.

가장 단순한 방법은 모든 구간을 순회하며 합을 구하는 방식이다.

하지만 이 경우 매번 합을 다시 계산해야 하고, 중복 계산이 많아진다.

2. 아이디어

위 그림과 같이 먼저 그룹을 잡은 후

위 그림처럼 앞에 값을 빼고 뒤에 값을 추가하는 방식이 바로 Sliding Window 개념이다.

슬라이딩 윈도우는 구간을 한 칸씩 옮겨가면서, 맨 앞 원소는 빼고 새로 들어온 원소는 더하는 방식으로 합을 업데이트한다. 그 과정을 통해 불필요한 중복 연산을 줄일 수 있다.

3. 코드 예시

def max_sum_subarray(nums, k):	# 리스트, 몇 개의 합으로 할지
    window_sum = sum(nums[:k])  # 초기 윈도우 합
    max_sum = window_sum		

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # 9 출력

• 동작 과정

  ▶ 초기 합: (2 + 1 + 5) = 8

  ▶ 다음 윈도우: 8 - 2 + 1 = 7

  ▶ 다음 윈도우: 7 - 1 + 3 = 9

  ▶ 최종 결과: 9

4. 응용 예시

1) Fixed-size Window (고정 길이)

길이 k인 모든 연속 구간의 합/평균/최댓값 등을 구할 때 사용.

def max_sum_subarray(nums, k):
    if k <= 0 or k > len(nums):
        return None
    window_sum = sum(nums[:k])
    ans = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        ans = max(ans, window_sum)
    return ans

# 예시
# [2,1,5,1,3,2], k=3  -> 최대 합 9

i) 시간 복잡도: 초기 합 O(k) + 각 이동당 O(1) 갱신 × (n-k) ≈ O(n)
ii) 공간 복잡도: 누적합/보조구조 미사용 시 O(1)

2) Variable-size Window (가변 길이)

윈도우 길이가 조건에 따라 늘었다 줄었다. left와 right 포인터 사용.
원칙: 조건을 만족할 때까지 right 확장 → 조건이 깨지면 left 축소.

(a) 중복 없는 최장 부분문자열 길이

def length_of_longest_substring(s):
    seen = set()
    left = 0
    ans = 0
    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        ans = max(ans, right - left + 1)
    return ans

# "abcabcbb" -> 3

i) 각 문자는 set에 들어가고(추가) 나가는(삭제) 일이 최대 1번 → O(n)

ii) 공간: 문자 종류 수에 비례, O(min(n, |Σ|))

(b) 서로 다른 문자가 최대 K개인 최장 부분문자열

from collections import Counter

def longest_substring_k_distinct(s, k):
   freq = Counter()
   left = 0
   distinct = 0
   ans = 0
   for right, ch in enumerate(s):
       freq[ch] += 1
       if freq[ch] == 1:
           distinct += 1
       while distinct > k:
           freq[s[left]] -= 1
           if freq[s[left]] == 0:
               distinct -= 1
           left += 1
       ans = max(ans, right - left + 1)
   return ans

# "eceba", k=2 -> 3 ("ece")

i) 각 문자가 카운터에 들어갔다 나오는 횟수 ≤ 1 → O(n)

ii) 공간 O(k) (최대 k개의 키만 유지되지는 않지만, 유효 구간 내에서만 의미)

3) Window 내 최댓값/최솟값 (Monotonic Queue)

고정 길이 k 윈도우에서 매 이동마다 최댓값이 필요하면, 단순히 max()를 매번 구하면 O(k)라 전체 O(nk).
대신 단조 deque로 O(n) 가능.

from collections import deque

def sliding_window_max(nums, k):
    if k <= 0 or k > len(nums):
        return []
    dq = deque()  # 인덱스를 저장, 값이 내림차순을 유지
    ans = []

    for i, x in enumerate(nums):
        # 뒤에서부터 현재 값보다 작은 값들은 필요 없음
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)

        # 윈도우에서 벗어난 인덱스 제거
        if dq[0] <= i - k:
            dq.popleft()

        # 첫 완성 윈도우부터 결과 기록
        if i >= k - 1:
            ans.append(nums[dq[0]])
    return ans

# [1,3,-1,-3,5,3,6,7], k=3 -> [3,3,5,5,6,7]

i) 시간 복잡도: 각 인덱스는 deque에 최대 1회 push, 1회 pop → O(n)
ii) 공간 복잡도: deque 최대 길이 k → O(k)

5. 정리

1) 왜 빠른가? (중복 제거 관점)

• 인접한 두 윈도우의 차이는 나가는 1개와 들어오는 1개뿐. 그렇기 때문에 이 차이만을 반영해 갱신하면, 매 스텝이 상수 시간으로 떨어진다.

2) 구현 팁 (자주 틀리는 포인트)

• 경계: right - left + 1이 길이. 인덱스 포함/제외 일관성 유지.

• 조건 불변식: while로 깨진 조건을 복구하고 나서 결과 갱신
  예) “윈도우 안에는 중복이 없다”를 항상 참으로 유지.

• 빈도 0 처리: Counter[ch] == 0일 때 키 정리(필요 시 del 또는 별도 카운터).

• 예외 입력: k <= 0, k > n, 빈 배열/빈 문자열은 미리 처리.

3) Sliding Window vs Two Pointers

• 슬라이딩 윈도우: 연속 구간 유지가 핵심. 윈도우 내부 상태(합/빈도/최댓값)를 상수 시간으로 갱신.

• 투 포인터(일반): 정렬 배열에서 합/차 등 전역 조건에 맞춰 양 끝 포인터를 조정하는 패턴. 윈도우의 “모든 구간” 탐색이 목적은 아님.

4) 대체/보완 아이디어

• Prefix Sum: 구간 합만 필요하면 더 간단(구간합 O(1)), 하지만 최댓값/빈도/제약 조건에는 부적합.

• Binary Search on Answer + Greedy/Check: 길이나 값이 단조 조건을 만족할 때 고려.

• 해시/빈도맵 + 윈도우: “제약을 만족하는 최장/최단 구간” 패턴에 기본 조합.