Ch.2 배열과 문자열
Sliding Window — 윈도우를 밀며 최적해 찾기
창문을 밀듯이 배열을 훑는 기법이 있다면?
기차 창문 밖을 보세요. 풍경이 슬라이드하듯 지나갑니다. 창문 크기는 고정인데 보이는 풍경은 계속 바뀌죠.
부분 배열의 합/최대/최소를 매번 다시 계산해야 할까?
윈도우를 한 칸 밀 때마다 빠지는 원소를 빼고 새 원소를 더하면 O(1)에 갱신됩니다!
핵심 개념
Sliding Window
고정/가변 크기 윈도우를 밀며 부분 배열을 효율적으로 탐색하는 기법
Fixed Window
윈도우 크기가 고정된 경우 (예: 연속 k개의 합)
Variable Window
조건에 따라 윈도우 크기가 변하는 경우
핵심 내용
기차 창문을 떠올려보세요. 풍경이 슬라이드하듯 지나갑니다
가장 간단한 슬라이딩 윈도우: 연속 k개 원소의 최대합 구하기
def max_sum_subarray(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_sum_subarray([2, 1, 5, 1, 3, 2], 3)) # 9 (5+1+3)매번 k개를 다시 더하면 O(n×k), 슬라이딩으로 갱신하면 O(n)!
면접 필수 문제! 중복 없는 가장 긴 부분 문자열을 찾아봅시다
Longest Substring Without Repeating Characters 입력: "abcabcbb" 출력: 3 ("abc") 핵심: set으로 윈도우 내 문자 추적, 중복 발견 시 left 이동
def length_of_longest_substring(s):
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
# 중복 발견 시 left 이동
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")) # 3Fixed Sliding Window에서 윈도우를 한 칸 밀 때 갱신에 드는 시간복잡도는?
"abcabcbb"에서 중복 없는 가장 긴 부분 문자열의 길이는?
Sliding Window에서 윈도우를 밀 때: window_sum += arr[i] - arr[i - ____]
Sliding Window에서 윈도우를 밀 때: window_sum += arr[i] - arr[i - ____]
Sliding Window 마스터
핵심 용어
Fixed Window
크기 고정 — 연속 k개의 최대합 등
Variable Window
크기 가변 — 조건 만족하는 최소/최대 구간
갱신 원리
윈도우 이동 시 빠지는 것 빼고, 들어오는 것 더함
정리 노트
Sliding Window — 윈도우를 밀며 최적해 찾기
두 가지 유형
- Fixed Window
- 크기 k 고정, 합/평균/최대 갱신 — O(n)
- Variable Window
- 조건 만족하는 최소/최대 구간 — left를 조건부 이동
대표 문제
- 연속 k개 최대합
- window += arr[i] - arr[i-k]
- Longest Substring
- set + while 중복 제거 → 가변 윈도우
면접 키워드: 'Sliding window로 O(n×k) → O(n) 최적화, 부분 배열/문자열 문제'
시각 자료
핵심 정리
- 1Fixed Window: 크기 고정, O(1) 갱신
- 2Variable Window: set/dict로 조건 추적
- 3Longest Substring Without Repeating → O(n)
- 4Brute force O(n²/n³) → Sliding Window O(n)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작