슬라이딩 윈도우는 배열이나 문자열에서 연속된 구간을 유지하며 답을 찾는 방식입니다. 투 포인터와 비슷해 보이지만, 핵심은 지금 보고 있는 구간을 매번 처음부터 다시 계산하지 않는 것입니다.
완전탐색은 모든 구간을 새로 계산하지만, 슬라이딩 윈도우는 왼쪽에서 빠지는 값과 오른쪽에서 들어오는 값만 갱신합니다. 이 차이만 이해해도 많은 구간 문제의 시간복잡도를 줄일 수 있습니다.
슬라이딩 윈도우는 구간을 유지하는 사고법이다
슬라이딩 윈도우에서 window는 현재 보고 있는 연속 구간입니다. 배열 [1, 3, 2, 5, 4]에서 길이 3 구간을 본다면 처음에는 [1, 3, 2], 다음에는 [3, 2, 5], 그다음에는 [2, 5, 4]처럼 창이 오른쪽으로 이동합니다.
중요한 점은 두 번째 구간의 합을 다시 3+2+5로 계산하지 않는다는 것입니다. 이전 합에서 빠진 1을 빼고 새로 들어온 5를 더하면 됩니다.
고정 길이 슬라이딩 윈도우
고정 길이 문제는 창의 크기가 k로 정해져 있습니다. 대표 문제는 길이 k인 연속 부분 배열의 최대 합입니다.
def max_sum_of_k(nums: list[int], k: int) -> int:
window_sum = sum(nums[:k])
answer = window_sum
for right in range(k, len(nums)):
window_sum += nums[right]
window_sum -= nums[right - k]
answer = max(answer, window_sum)
return answer처음 k개 합만 한 번 구한 뒤, 이후에는 들어오는 값과 나가는 값만 반영합니다. 그래서 모든 구간을 매번 합산하는 O(nk) 풀이를 O(n)으로 줄일 수 있습니다.
가변 길이 슬라이딩 윈도우
가변 길이 문제는 창 크기가 고정되어 있지 않습니다. 조건을 만족할 때까지 오른쪽 포인터를 늘리고, 조건을 만족한 뒤에는 왼쪽 포인터를 당기며 더 좋은 답을 찾습니다.
def min_len_at_least(target: int, nums: list[int]) -> int:
left = 0
total = 0
answer = float("inf")
for right, value in enumerate(nums):
total += value
while total >= target:
answer = min(answer, right - left + 1)
total -= nums[left]
left += 1
return 0 if answer == float("inf") else answer여기서는 right가 한 번씩 이동하고 left도 전체 과정에서 한 번씩만 이동합니다. while 문이 있어도 전체 이동 횟수는 O(n)에 가깝게 제한됩니다.
투 포인터와 무엇이 다를까
투 포인터는 두 개의 인덱스를 움직이며 탐색 범위를 줄이는 넓은 기법입니다. 정렬된 배열에서 양끝 포인터를 좁혀 합을 찾는 문제도 투 포인터입니다.
슬라이딩 윈도우는 투 포인터 중에서도 연속 구간을 유지하고 그 구간의 합, 개수, 빈도 같은 상태를 갱신하는 유형에 가깝습니다.
- 투 포인터: 두 인덱스를 움직이는 넓은 전략
- 슬라이딩 윈도우: 연속 구간 상태를 유지하며 갱신하는 전략
- 고정 길이 윈도우: 창 크기가 변하지 않는다
- 가변 길이 윈도우: 조건에 따라 창을 늘리고 줄인다
문제를 보고 떠올리는 신호
- 연속된 부분 배열 또는 부분 문자열이라는 말이 나온다
- 구간 합, 구간 개수, 특정 조건을 만족하는 최소/최대 길이를 묻는다
- 모든 구간을 직접 확인하면 O(n^2) 이상이 된다
- 오른쪽으로 한 칸 이동할 때 이전 계산을 재사용할 수 있다
- 구간 안의 빈도표나 합을 유지하면 조건 판단이 가능하다
문자열 중복 문자 문제
문자열에서도 슬라이딩 윈도우가 자주 쓰입니다. 예를 들어 중복 문자가 없는 가장 긴 부분 문자열은 현재 창 안의 문자 빈도를 유지하며 풀 수 있습니다.
def longest_unique(s: str) -> int:
left = 0
seen = set()
answer = 0
for right, ch in enumerate(s):
while ch in seen:
seen.remove(s[left])
left += 1
seen.add(ch)
answer = max(answer, right - left + 1)
return answer새 문자가 이미 창 안에 있으면 중복이 사라질 때까지 왼쪽을 당깁니다. 이때 set은 현재 창의 상태를 나타냅니다.
자주 하는 실수
- 고정 길이 문제에서 창 크기를 유지하지 못한다
- 가변 길이 문제에서 조건을 만족한 뒤 한 번만 줄이고 멈춘다
- 음수가 있는 구간 합 문제에 단순 sliding window를 그대로 적용한다
- left가 이동할 때 빈도표나 합에서 빠진 값을 제거하지 않는다
- 연속 구간이 아닌 조합 문제에 억지로 적용한다
정리
슬라이딩 윈도우는 연속 구간을 계속 새로 계산하지 않고, 이전 구간의 상태를 재사용하는 방법입니다. 투 포인터와 겹치지만 목적은 구간 상태 유지에 더 가깝습니다.
기본 투 포인터 사고는 투 포인터 알고리즘 글과 이어서 보면 좋습니다. 배열과 리스트의 기본 동작은 Python data structures 문서에서 확인할 수 있습니다.
