슬라이딩 윈도우 | 부분 배열 최적화 기법 완벽 정리
이 글의 핵심
알고리즘 슬라이딩 윈도우는 고정·가변 길이의 연속 구간을 한 칸씩 밀며 O(n)으로 갱신하는 기법입니다. 이 글에서는 고정·가변 윈도우를 구분하고, 합·최댓값·문자열 조건 문제에서의 패턴과 투 포인터와의 차이를 예제로 정리합니다.
들어가며
연속 부분 배열이나 부분 문자열의 합·조건을 매번 처음부터 다시 계산하면 시간 초과가 나기 쉽습니다. 이 글에서는 윈도우를 한 칸씩 밀며 갱신하는 방식으로 복잡도를 줄이는 흐름을 단계적으로 익힐 수 있습니다.
”윈도우를 슬라이딩하며 최적화”
슬라이딩 윈도우는 연속된 부분 배열을 효율적으로 처리하는 기법입니다.
1. 고정 크기 윈도우
기본 패턴
def max_sum_subarray(arr, k):
"""
크기 k인 부분 배열의 최대 합
[1, 4, 2, 10, 23, 3, 1, 0, 20], k=4 → 39
"""
if len(arr) < k:
return None
# 첫 윈도우 합
window_sum = sum(arr[:k])
max_sum = window_sum
# 윈도우 이동
for i in range(k, len(arr)):
window_sum = window_sum - arr[i - k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sum
# 테스트
arr = [1, 4, 2, 10, 23, 3, 1, 0, 20]
print(max_sum_subarray(arr, 4)) # 39 (10+23+3+1)2. 가변 크기 윈도우
최소 길이 부분 배열
def min_subarray_len(arr, target):
"""
합이 target 이상인 최소 길이 부분 배열
[2,3,1,2,4,3], target=7 → 2 ([4,3])
"""
left = 0
current_sum = 0
min_len = float('inf')
for right in range(len(arr)):
current_sum += arr[right]
# 조건 만족 시 윈도우 축소
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= arr[left]
left += 1
return min_len if min_len != float('inf') else 0
# 테스트
arr = [2, 3, 1, 2, 4, 3]
print(min_subarray_len(arr, 7)) # 2고정 크기 vs 가변 크기 윈도우
| 구분 | 고정 크기 | 가변 크기 |
|---|---|---|
| 윈도우 길이 | k 등으로 항상 동일 | 조건(합, 중복, 카운트)에 따라 늘었다 줄었다 |
| 전형적 루프 | right만 전진하고, right - left + 1 == k일 때 한 칸씩 left도 전진 | right로 확장하고, 조건 깨질 때까지 left로 축소 |
| 대표 문제 | 크기 k인 부분 배열 합·최댓값, 고정 길이 애너그램 | 최소 길이 부분합, 중복 없는 최장 부분 문자열, 최소 윈도우 부분 문자열 |
| 투 포인터와 | left = right - k + 1로도 표현 가능 | 아래 “확장·축소 패턴”과 동일한 두 포인터 사고 |
둘 다 left, right가 앞으로만 가는 “같은 방향 두 포인터”이며, 차이는 길이가 고정인지입니다.
3. 실전 문제
문제 1: 최대 연속 1의 개수
def longest_ones(arr, k):
"""
최대 k개의 0을 1로 바꿀 때 최대 연속 1의 개수
[1,1,1,0,0,0,1,1,1,1,0], k=2 → 6
"""
left = 0
zero_count = 0
max_len = 0
for right in range(len(arr)):
if arr[right] == 0:
zero_count += 1
# 0이 k개 초과 시 윈도우 축소
while zero_count > k:
if arr[left] == 0:
zero_count -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
# 테스트
arr = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
print(longest_ones(arr, 2)) # 6문제 2: 최장 부분 문자열
def length_of_longest_substring(s):
"""
중복 문자 없는 최장 부분 문자열
"abcabcbb" → 3 ("abc")
"""
char_set = set()
left = 0
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
print(length_of_longest_substring("bbbbb")) # 1
print(length_of_longest_substring("pwwkew")) # 3문제 3: 애너그램 찾기
from collections import Counter
def find_anagrams(s, p):
"""
문자열 s에서 p의 애너그램 시작 인덱스
s="cbaebabacd", p="abc" → [0, 6]
"""
result = []
p_count = Counter(p)
window_count = Counter()
left = 0
for right in range(len(s)):
window_count[s[right]] += 1
# 윈도우 크기 유지
if right - left + 1 > len(p):
window_count[s[left]] -= 1
if window_count[s[left]] == 0:
del window_count[s[left]]
left += 1
# 애너그램 확인
if window_count == p_count:
result.append(left)
return result
# 테스트
print(find_anagrams("cbaebabacd", "abc"))
# [0, 6]대표 문제 (LeetCode): 최장 부분 문자열 · 최소 윈도우 · 고정 합
아래 세 가지는 슬라이딩 윈도우를 공부할 때 거의 필수로 거론되는 유형입니다. (이 글 앞쪽 예제와 연결해 읽으면 좋습니다.)
| 문제 | 유형 | 핵심 |
|---|---|---|
| 3. Longest Substring Without Repeating Characters | 가변, 조건: 중복 없음 | right 추가 → 중복 시 left를 당겨서 중복 제거 |
| 76. Minimum Window Substring | 가변, need/cover | right로 need 충족까지 확장 → 최소가 되도록 left 축소 |
| 643. Maximum Average Subarray I (또는 합 최대) | 고정 길이 k | 한 칸 밀 때 sum -= out, sum += in, O(n) |
Minimum Window Substring 스케치 (Python)
from collections import Counter
def min_window(s: str, t: str) -> str:
need = Counter(t)
missing = len(t)
left = 0
best = (float("inf"), None, None) # 길이, 시작, 끝
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0:
if right - left + 1 < best[0]:
best = (right - left + 1, left, right)
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if best[1] is None else s[best[1] : best[2] + 1](실제 제출 시에는 need/window를 나누어 쓰는 방식도 많습니다. 위는 “missing 카운트로 조건 충족”을 강조한 최소 예입니다.)
시간 복잡도 분석
- 브루트 포스
모든 연속 구간[left, right]를 이중 루프로 보면 O(n²)~O(n³)입니다. - 슬라이딩 윈도우
left와right가 각각 최대 n번만 앞으로 이동하면 전체 O(n)입니다. (한 번의right전진에left가 여러 번 움직여도,left가 돌아가지 않으므로 합쳐서 선형입니다.) - 맵/카운터
문자·빈도를 유지하면 삽입·갱신이 문제당 O(1)~O(σ) (알파벳 크기 σ)이고, 보통 O(n) 또는 O(n·σ)로 표현합니다. - 고정 크기 k
초기 합 O(k) + 슬라이드 O(n−k) → O(n).
윈도우 확장·축소 조건 패턴
- 확장 (
right++)
항상 한 칸 넓혀서 현재 구간에 원소를 포함합니다. 고정 윈도우는right만 순차 증가하고, 가변은 “조건을 만족시키기 위해” 넓힙니다. - 축소 (
left++)- 고정 크기:
right - left + 1 > k이면 왼쪽을 한 칸 당겨 길이 k 유지. - 가변 — 유효하지 않을 때: 예) 중복 문자, 0이 너무 많음, need 미충족이 아닌 “최소 길이” 찾기 전 단계 등.
- 가변 — 유효한데 더 짧게 줄일 수 있을 때: Minimum Window에서 need 충족 후
left를 당겨 최소 길이 갱신.
- 고정 크기:
- 불변식(invariant)
“윈도우가 만족해야 할 조건”을 한 문장으로 적어 두면, 언제 while로left를 당길지가 명확해집니다. (예: “중복 문자가 없을 때까지left이동”.)
실전 팁
슬라이딩 윈도우 패턴
# 패턴 1: 고정 크기
left = 0
for right in range(len(arr)):
add(arr[right])
if right - left + 1 == k:
process_window()
remove(arr[left])
left += 1
# 패턴 2: 가변 크기
left = 0
for right in range(len(arr)):
add(arr[right])
while not is_valid():
remove(arr[left])
left += 1
update_result()정리
핵심 요약
- 슬라이딩 윈도우: 연속 부분 배열 O(n) 처리
- 고정 크기: 윈도우 크기 일정
- 가변 크기: 조건에 따라 확장/축소
- 최적화: O(n²) → O(n)
추천 문제
백준:
프로그래머스:
LeetCode:
관련 글
- 그리디 알고리즘 |
- 알고리즘 시리즈 전체 목차
- 배열과 리스트
- 스택과 큐