부분 문자열을 위한 슬라이딩 윈도우
중복 문자가 없는 가장 긴 부분 문자열과 모든 대상 문자를 포함하는 최소 윈도우를 찾는 가변 크기 슬라이딩 윈도우를 구현합니다.
부분 문자열을 위한 슬라이딩 윈도우은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
슬라이딩 윈도우 개념
슬라이딩 윈도우는 왼쪽 포인터와 오른쪽 포인터 사이의 부분 배열(또는 부분 문자열)을 유지합니다. 가능한 모든 부분 배열의 특성을 매번 처음부터 O(n²)으로 다시 계산하는 대신, 윈도우는 요소 하나를 추가하여 오른쪽으로 확장하고 요소 하나를 제거하여 왼쪽으로 축소하면서 단계마다 O(1)로 현재 상태를 유지합니다. 그 결과 O(n) 알고리즘을 만들 수 있습니다. 배열을 뒤로 가지 않고 앞으로 이동하기 때문에 '슬라이딩' 윈도우라고 부릅니다.
# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
window_sum = sum(nums[:k]) # initial window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] # add new right
window_sum -= nums[i - k] # remove old left
best = max(best, window_sum)
return best
print(max_sum_window([2,1,5,1,3,2], 3)) # 9 ([5,1,3])고정 크기 윈도우와 가변 크기 윈도우
슬라이딩 윈도우에는 두 가지 유형이 있습니다. 고정 크기 윈도우에서는 두 포인터가 같은 속도로 이동하며 윈도우에는 항상 정확히 k개의 요소가 들어 있습니다. 가변 크기 윈도우에서는 오른쪽 포인터가 탐욕적으로 확장되고, 윈도우가 제약 조건을 위반할 때만 왼쪽 포인터가 축소합니다. 가변 크기 윈도우는 최적의 윈도우 크기를 미리 알 수 없는 '반복되는 문자가 없는 가장 긴 부분 문자열'과 같은 문제를 해결합니다.
# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
freq[s[right]] += 1
while len(freq) > k: # window invalid: shrink
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_k_distinct('eceba', 2)) # 3 ('ece')
print(longest_k_distinct('aa', 1)) # 2반복되는 문자가 없는 가장 긴 부분 문자열
가장 유명한 가변 슬라이딩 윈도우 문제입니다. 현재 윈도우에 있는 문자를 추적하려면 집합을 사용합니다. 오른쪽으로 확장하다가 중복 문자를 발견하면, 해당 중복 문자가 제거될 때까지 왼쪽에서 윈도우를 축소합니다. 더 빠른 방법에서는 각 문자의 가장 최근 인덱스를 저장하는 해시 맵을 사용하므로, 왼쪽 포인터를 조금씩 이동하는 대신 한 번에 중복 문자 다음으로 건너뛸 수 있습니다.
def length_of_longest_substring(s):
char_idx = {} # char -> last seen index
left = 0
best = 0
for right, c in enumerate(s):
if c in char_idx and char_idx[c] >= left:
left = char_idx[c] + 1 # jump past duplicate
char_idx[c] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring('abcabcbb')) # 3 ('abc')
print(length_of_longest_substring('bbbbb')) # 1
print(length_of_longest_substring('pwwkew')) # 3 ('wke')최소 윈도우 부분 문자열
문자열 s와 t가 주어졌을 때, t의 모든 문자를 포함하는 s의 가장 작은 윈도우를 찾습니다. 두 개의 빈도 맵을 사용합니다. need는 필요한 문자를, have는 현재 윈도우에서 요구 사항을 충족하는 문자를 나타냅니다. t에서 충족된 서로 다른 문자의 수를 formed 카운터로 추적합니다. 오른쪽으로 확장하여 문자를 포함시키고, t 전체가 포함되면 왼쪽을 축소하여 윈도우를 최소화합니다. 시간 복잡도는 O(|s| + |t|)입니다.
from collections import Counter
def min_window(s, t):
if not t or not s: return ''
need = Counter(t)
have = {}
formed = 0
required = len(need)
left = 0
best = float('inf'), 0, 0
for right, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = right - left + 1, left, right
have[s[left]] -= 1
if s[left] in need and have[s[left]] < need[s[left]]:
formed -= 1
left += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
print(min_window('ADOBECODEBANC', 'ABC')) # 'BANC'슬라이딩 윈도우 템플릿
대부분의 가변 슬라이딩 윈도우 문제는 다음 템플릿을 공유합니다. 오른쪽으로 확장하여 새 문자를 포함하고, 윈도우 상태를 업데이트한 다음, 유효성을 확인합니다. 유효하지 않다면 다시 유효해질 때까지 왼쪽에서 축소합니다. 핵심은 왼쪽 포인터가 뒤로 가지 않고 오직 앞으로만 이동한다는 점입니다. 따라서 모든 축소 단계에 걸리는 총 작업량은 O(n)입니다. 윈도우는 각 요소를 최대 두 번 방문합니다(한 번은 추가할 때, 한 번은 제거할 때).
def sliding_window_template(s, condition_check, update_state, remove_state):
"""
Generic sliding window skeleton.
Adapt condition_check, update_state, remove_state per problem.
"""
left = 0
state = {} # or whatever state you need
best = 0
for right in range(len(s)):
update_state(state, s[right]) # expand window
while not condition_check(state): # window invalid
remove_state(state, s[left]) # shrink window
left += 1
best = max(best, right - left + 1)
return best문자열 속 순열
패턴 p의 순열 중 하나가 s의 부분 문자열로 존재하는지 확인합니다. 순열 확인은 p와 동일한 문자 빈도를 가진 윈도우를 찾는 것과 같습니다. 정확히 len(p)개의 문자를 포함하는 슬라이딩 윈도우를 유지하고 빈도 수를 비교합니다. 매 단계에서 전체 Counter 객체를 비교하는 비용은 O(26)이며(소문자 영어에서는 상수), 전체 시간 복잡도는 O(n × 26) = O(n)입니다.
from collections import Counter
def check_inclusion(p, s):
if len(p) > len(s): return False
need = Counter(p)
window = Counter(s[:len(p)])
if need == window: return True
for right in range(len(p), len(s)):
left = right - len(p)
window[s[right]] += 1
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
if window == need:
return True
return False
print(check_inclusion('ab', 'eidbaooo')) # True ('ba')
print(check_inclusion('ab', 'eidboaoo')) # False애너그램 부분 문자열 모두 세기
s에서 p의 애너그램이 시작되는 모든 인덱스를 찾습니다. 문자열 속 순열 문제와 동일한 고정 윈도우 기법을 사용하지만, 첫 번째 일치에서 True를 반환하는 대신 일치하는 모든 위치를 수집합니다. 윈도우 크기는 len(p)로 고정되며, s 전체를 따라 윈도우를 이동하면서 매 단계 빈도 수를 비교합니다.
from collections import Counter
def find_anagrams(s, p):
result = []
need = Counter(p)
k = len(p)
window = Counter(s[:k])
if window == need:
result.append(0)
for right in range(k, len(s)):
window[s[right]] += 1
left_char = s[right - k]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == need:
result.append(right - k + 1)
return result
print(find_anagrams('cbaebabacd', 'abc')) # [0, 6]서로 다른 문자가 최대 2개인 가장 긴 부분 문자열
슬라이딩 윈도우의 변형입니다. 서로 다른 문자를 최대 2개 포함하는 가장 긴 부분 문자열을 찾습니다. 현재 윈도우에 있는 문자의 빈도 맵을 유지합니다. 맵의 항목이 2개를 초과하면 제약 조건이 다시 충족될 때까지 왼쪽 포인터를 오른쪽으로 이동합니다(빈도를 감소시키고, 0이 되면 삭제합니다). 이는 k=2인 '서로 다른 문자가 최대 k개' 문제의 특수한 경우입니다.
def longest_substring_two_distinct(s):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > 2:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_substring_two_distinct('eceba')) # 3 ('ece')
print(longest_substring_two_distinct('ccaabbb')) # 5 ('aabbb')슬라이딩 윈도우 최댓값
크기가 k인 모든 윈도우에서 최댓값을 찾습니다. 각 윈도우의 최댓값을 무차별 대입으로 확인하면 O(n×k)이 걸립니다. 최적의 방법은 인덱스를 저장하는 단조 덱을 사용하는 것입니다. 덱을 내림차순으로 유지하면 맨 앞에는 항상 현재 윈도우 최댓값의 인덱스가 옵니다. 윈도우를 벗어난 인덱스는 맨 앞에서 제거하고, 더 큰 요소가 들어오면 맨 뒤에서 인덱스를 제거합니다. 전체 시간 복잡도는 O(n)입니다.
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1: # window is full
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]슬라이딩 윈도우를 사용하는 경우
다음과 같은 경우에는 슬라이딩 윈도우를 고려하시기 바랍니다:
- 제약 조건이 있는 부분 문자열 또는 부분 배열(최대 길이, 합 = k, 서로 다른 문자가 최대 k개)
- 집계가 필요한 고정 윈도우 크기(최댓값, 합, 빈도)
- 연속 범위 문제(임의의 부분 집합이 아님)
# Recognising sliding window problems:
# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
s = sum(nums[:k])
best = s
for i in range(k, len(nums)):
s += nums[i] - nums[i-k]
best = max(best, s)
return best / k
print(max_avg([1,12,-5,-6,50,3], 4)) # 12.75
# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
left = s = 0
best = float('inf')
for right, n in enumerate(nums):
s += n
while s >= target:
best = min(best, right - left + 1)
s -= nums[left]; left += 1
return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3])) # 2유효한 윈도우 세기: 최대 K
일부 문제에서는 조건을 만족하는 부분 배열의 개수를 묻습니다. 유용한 방법은 서로 다른 문자가 최대 k개인 부분 배열을 센 다음, 이를 빼서 정확히 k개인 경우를 구하는 것입니다: exactly(k) = at_most(k) - at_most(k-1). at_most를 호출할 때마다 O(n)이 걸리므로 전체 시간 복잡도는 O(n)입니다. at_most 함수는 서로 다른 문자의 수가 k를 넘지 않는 윈도우를 셉니다. 각 오른쪽 끝점에 대해 유효한 모든 왼쪽 끝점의 수인 right - left + 1을 더하는 방식입니다.
from collections import defaultdict
def subarrays_at_most_k(s, k):
freq = defaultdict(int)
left = 0
count = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0: del freq[s[left]]
left += 1
count += right - left + 1 # all valid windows ending at right
return count
def subarrays_exactly_k(s, k):
return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)
print(subarrays_exactly_k('araaci', 2)) # 9빠른 확인
이번 레슨에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보시기 바랍니다.
레슨 요약
이번 레슨에서는 다음을 배웠습니다. 슬라이딩 윈도우는 요소가 들어오고 나갈 때 실행 중인 윈도우 상태를 O(1)에 업데이트하여 O(n²)의 비용을 없앱니다. 또한 고정 크기 윈도우에서는 두 포인터가 같은 속도로 이동하고, 가변 크기 윈도우에서는 오른쪽으로 탐욕적으로 확장하다가 제약 조건을 위반할 때만 왼쪽으로 축소합니다. 그리고 최소 윈도우 부분 문자열과 문자열 속 순열 문제는 모두 빈도 맵으로 관리하는 윈도우 상태를 사용하며, 현재 충족된 필수 문자의 수를 카운터로 추적합니다. 다음에는 애너그램과 문자 빈도 맵을 살펴보겠습니다.
자주 묻는 질문
“부분 문자열을 위한 슬라이딩 윈도우” 강의는 무료인가요?
네 — “부분 문자열을 위한 슬라이딩 윈도우” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“부분 문자열을 위한 슬라이딩 윈도우”에서 뭘 배우나요?
중복 문자가 없는 가장 긴 부분 문자열과 모든 대상 문자를 포함하는 최소 윈도우를 찾는 가변 크기 슬라이딩 윈도우를 구현합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“부분 문자열을 위한 슬라이딩 윈도우” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 면접을 위한 Python 문자열 API
- 부분 문자열을 위한 슬라이딩 윈도우
- 애너그램과 문자 빈도 맵
- 문자열 인코딩, 뒤집기, 회문