슬라이딩 윈도우(Sliding Window)는 고정 크기 또는 가변 크기의 창(Window)을 배열 위에 이동시켜 구간 문제를 O(n)에 해결하는 기법이다. 중첩 반복문 O(n²)을 O(n)으로 줄인다.
고정 크기 윈도우
python
# 크기 k인 부분 배열의 최대 합
def max_subarray_sum(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i-k] # 창 이동
max_sum = max(max_sum, window_sum)
return max_sum
print(max_subarray_sum([2,1,5,1,3,2], 3)) # 9 (5+1+3)
가변 크기 윈도우
python
# 합이 target 이상인 최소 길이 부분 배열
def min_subarray_len(target, nums):
left = 0
current_sum = 0
min_len = float('inf')
for right in range(len(nums)):
current_sum += nums[right]
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0
중복 없는 최장 부분 문자열
python
def length_of_longest_substring(s):
char_set = set()
left = max_len = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left]); left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
print(length_of_longest_substring("abcabcbb")) # 3 (abc)
관련 개념
- •투 포인터 — 유사한 기법
- •덱 — 슬라이딩 윈도우 최댓값에 활용
참고문헌
- •LeetCode Sliding Window 패턴
