Updated Feb 6, 2026
들어가며
코딩 테스트에서 배열이나 문자열의 연속된 부분을 다루는 문제를 만나면 어떻게 접근하시나요? 가장 직관적인 방법은 모든 부분 배열을 이중 반복문으로 확인하는 것이지만, 이는 O(N²) 시간 복잡도를 가져 입력 크기가 커지면 시간 초과를 유발합니다.
이때 슬라이딩 윈도우(Sliding Window) 패턴을 사용하면 O(N) 시간 복잡도로 극적인 최적화가 가능합니다. 이 글에서는 슬라이딩 윈도우의 핵심 원리부터 실전 활용법까지 완전히 정복해보겠습니다.
슬라이딩 윈도우란?
핵심 개념
슬라이딩 윈도우는 고정 또는 가변 크기의 “창(window)”을 배열 위에서 미끄러지듯 이동시키며 문제를 해결하는 기법입니다. 창문을 좌우로 밀어 움직이는 모습을 상상하면 이해하기 쉽습니다.
핵심 아이디어: 매번 전체 구간을 다시 계산하지 않고, 이전 계산 결과를 재활용하면서 한 칸씩 이동한다.
적용 가능한 문제 유형
슬라이딩 윈도우는 다음 조건을 만족하는 문제에 효과적입니다:
- 연속된 부분 배열/문자열을 다루는 문제
- 최대/최소값, 합계, 평균 등을 구하는 문제
- 특정 조건을 만족하는 부분 배열 찾기
- 중복 문자 없는 최장 부분 문자열 등
슬라이딩 윈도우의 두 가지 유형
| 유형 | 특징 | 예시 문제 |
|---|---|---|
| 고정 크기 윈도우 | 창 크기가 처음부터 정해져 있음 | 크기 K인 부분 배열의 최대 합 |
| 가변 크기 윈도우 | 조건에 따라 창 크기가 동적으로 변함 | 합이 S 이상인 최소 길이 부분 배열 |
O(N²) vs O(N) 비교
문제 예시
문제: 크기가 N인 배열에서 연속된 K개 원소의 합이 최대인 값을 구하세요.
Brute Force 접근 (O(N²))
def max_sum_brute_force(arr, k):
"""
모든 크기 k 부분 배열의 합을 직접 계산
시간 복잡도: O(N * K) ≈ O(N²) (K가 N에 비례할 때)
"""
n = len(arr)
max_sum = float('-inf')
# 시작 위치를 0부터 n-k까지 이동
for i in range(n - k + 1):
current_sum = 0
# 매번 k개 원소를 다시 더함 (중복 계산)
for j in range(i, i + k):
current_sum += arr[j]
max_sum = max(max_sum, current_sum)
return max_sum
# 테스트
arr = [2, 1, 5, 1, 3, 2]
k = 3
print(max_sum_brute_force(arr, k)) # 9 (5+1+3)
문제점:
– [2, 1, 5]의 합을 구한 후, [1, 5, 1]의 합을 구할 때 1+5를 다시 계산
– 중복 계산이 반복되어 비효율적
슬라이딩 윈도우 접근 (O(N))
def max_sum_sliding_window(arr, k):
"""
슬라이딩 윈도우로 최적화
시간 복잡도: O(N)
공간 복잡도: O(1)
"""
n = len(arr)
if n < k:
return None
# 1. 첫 번째 윈도우의 합 계산
window_sum = sum(arr[:k])
max_sum = window_sum
# 2. 윈도우를 한 칸씩 이동하며 업데이트
for i in range(k, n):
# 왼쪽 끝 원소 제거, 오른쪽 새 원소 추가
window_sum = window_sum - arr[i - k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sum
# 테스트
arr = [2, 1, 5, 1, 3, 2]
k = 3
print(max_sum_sliding_window(arr, k)) # 9
동작 과정 시각화:
배열: [2, 1, 5, 1, 3, 2], k=3
Step 1: [2, 1, 5] → sum = 8
Step 2: [1, 5, 1] → sum = 8 - 2 + 1 = 7
Step 3: [5, 1, 3] → sum = 7 - 1 + 3 = 9 (최대)
Step 4: [1, 3, 2] → sum = 9 - 5 + 2 = 6
결과: 9
성능 비교표
| 항목 | Brute Force | Sliding Window |
|---|---|---|
| 시간 복잡도 | O(N × K) | O(N) |
| 공간 복잡도 | O(1) | O(1) |
| N=10,000, K=100 | 약 1,000,000 연산 | 약 10,000 연산 |
| 효율성 | ❌ 중복 계산 多 | ✅ 계산 재활용 |
고정 크기 윈도우 패턴
기본 템플릿
def fixed_window_template(arr, k):
"""
고정 크기 윈도우 기본 템플릿
"""
n = len(arr)
if n < k:
return None
# 1. 첫 윈도우 초기화
window_state = initialize_window(arr[:k])
result = process_window(window_state)
# 2. 윈도우 슬라이딩
for i in range(k, n):
# 왼쪽 제거
remove_from_window(window_state, arr[i - k])
# 오른쪽 추가
add_to_window(window_state, arr[i])
# 결과 갱신
result = update_result(result, window_state)
return result
실전 문제: 평균이 최대인 연속 부분 배열
def max_average_subarray(nums, k):
"""
LeetCode 643. Maximum Average Subarray I
크기 k인 부분 배열의 최대 평균 구하기
"""
# 최대 합을 구한 후 k로 나누면 최대 평균
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum / k # 평균 계산
# 테스트
print(max_average_subarray([1, 12, -5, -6, 50, 3], 4)) # 12.75
가변 크기 윈도우 패턴
핵심 전략
가변 크기 윈도우는 투 포인터(Two Pointers) 기법과 결합됩니다:
left,right두 포인터로 윈도우 범위 관리- 조건을 만족할 때:
right확장 (윈도우 키우기) - 조건을 위반할 때:
left축소 (윈도우 줄이기)
기본 템플릿
def variable_window_template(arr, condition):
"""
가변 크기 윈도우 기본 템플릿
"""
left = 0
window_state = initialize_state()
result = initial_result()
for right in range(len(arr)):
# 1. 오른쪽 원소를 윈도우에 추가
add_to_window(window_state, arr[right])
# 2. 조건 위반 시 왼쪽 축소
while violates_condition(window_state, condition):
remove_from_window(window_state, arr[left])
left += 1
# 3. 현재 윈도우로 결과 갱신
result = update_result(result, window_state, right - left + 1)
return result
실전 문제 1: 합이 S 이상인 최소 길이 부분 배열
def min_subarray_len(target, nums):
"""
LeetCode 209. Minimum Size Subarray Sum
합이 target 이상인 최소 길이 연속 부분 배열 길이 반환
시간 복잡도: O(N)
- 각 원소가 right, left 포인터에 의해 최대 2번 방문
공간 복잡도: O(1)
"""
left = 0
current_sum = 0
min_length = float('inf')
for right in range(len(nums)):
# 오른쪽 원소 추가
current_sum += nums[right]
# 조건 만족 시 왼쪽 축소하며 최소 길이 갱신
while current_sum >= target:
min_length = min(min_length, right - left + 1)
current_sum -= nums[left]
left += 1
return min_length if min_length != float('inf') else 0
# 테스트
print(min_subarray_len(7, [2, 3, 1, 2, 4, 3])) # 2 ([4, 3])
print(min_subarray_len(11, [1, 2, 3, 4, 5])) # 3 ([3, 4, 5])
동작 과정:
target=7, nums=[2, 3, 1, 2, 4, 3]
right=0: [2], sum=2 < 7
right=1: [2,3], sum=5 < 7
right=2: [2,3,1], sum=6 < 7
right=3: [2,3,1,2], sum=8 ≥ 7 → length=4
left=1: [3,1,2], sum=6 < 7 (축소 중단)
right=4: [3,1,2,4], sum=10 ≥ 7 → length=4
left=2: [1,2,4], sum=7 ≥ 7 → length=3
left=3: [2,4], sum=6 < 7
right=5: [2,4,3], sum=9 ≥ 7 → length=3
left=4: [4,3], sum=7 ≥ 7 → length=2 (최소!)
left=5: [3], sum=3 < 7
결과: 2
실전 문제 2: 중복 문자 없는 최장 부분 문자열
def length_of_longest_substring(s):
"""
LeetCode 3. Longest Substring Without Repeating Characters
중복 문자가 없는 최장 부분 문자열의 길이
시간 복잡도: O(N)
공간 복잡도: O(min(N, M)) - M은 문자 집합 크기
"""
char_index = {} # 문자의 최근 등장 위치 저장
left = 0
max_length = 0
for right in range(len(s)):
char = s[right]
# 중복 문자 발견 시 left 이동
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
# 현재 문자 위치 갱신
char_index[char] = right
# 최대 길이 갱신
max_length = max(max_length, right - left + 1)
return max_length
# 테스트
print(length_of_longest_substring("abcabcbb")) # 3 ("abc")
print(length_of_longest_substring("bbbbb")) # 1 ("b")
print(length_of_longest_substring("pwwkew")) # 3 ("wke")
동작 과정:
s = "abcabcbb"
right=0: 'a', window="a", length=1
right=1: 'b', window="ab", length=2
right=2: 'c', window="abc", length=3 (최대)
right=3: 'a' (중복!), left=1, window="bca", length=3
right=4: 'b' (중복!), left=2, window="cab", length=3
right=5: 'c' (중복!), left=3, window="abc", length=3
right=6: 'b' (중복!), left=5, window="cb", length=2
right=7: 'b' (중복!), left=7, window="b", length=1
결과: 3
시간 복잡도 분석
고정 크기 윈도우
for i in range(k, n): # N-K번 반복
window_sum = window_sum - arr[i-k] + arr[i] # O(1) 연산
- 시간 복잡도:
- 초기 윈도우 계산:
- 슬라이딩:
- 합계:
- 공간 복잡도: (추가 배열 불필요)
가변 크기 윈도우
for right in range(len(arr)): # N번 반복
# ...
while condition: # left는 전체적으로 최대 N번 이동
left += 1
- 시간 복잡도:
right포인터: 0 → N-1로 한 번 순회left포인터: 총 이동 거리 최대 N- 각 원소가 최대 2번 방문 (right 추가 1번, left 제거 1번)
- 중요: while 루프가 중첩되어 있지만 가 아님!
- 공간 복잡도: ~ (해시맵 사용 여부에 따라)
왜 O(N²)가 아닌가?
초보자들이 자주 하는 오해:
for right in range(n): # O(N)
while condition: # O(N)?
left += 1
# → O(N²)?
정답: left는 전체 실행 중 단조 증가하며 최대 N까지만 이동합니다.
| 반복 | right | left 이동 횟수 | 총 이동 |
|---|---|---|---|
| 1회 | 0 | 0 | 0 |
| 2회 | 1 | 1 | 1 |
| 3회 | 2 | 0 | 1 |
| 4회 | 3 | 2 | 3 |
| … | … | … | … |
| N회 | N-1 | ? | ≤ N |
핵심: while 루프는 매 반복마다 N번이 아니라, 전체 실행에서 총 N번만 실행됩니다.
이를 Amortized Analysis(분할 상환 분석)이라고 하며, 최종 시간 복잡도는 입니다.
난이도별 접근법
난이도: 쉬움
특징: 고정 크기 윈도우, 단순 합계/평균
# 예: 크기 K 윈도우의 최대 합
def easy_sliding_window(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
핵심 포인트:
– 윈도우 크기 고정
– 단순 덧셈/뺄셈 연산
– 엣지 케이스: len(arr) < k
난이도: 보통
특징: 가변 크기 윈도우, 조건부 확장/축소
# 예: 합이 target 이상인 최소 길이
def medium_sliding_window(arr, target):
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
핵심 포인트:
– 투 포인터 활용
– while 조건 설정 주의
– 최소/최대 길이 추적
난이도: 어려움
특징: 복잡한 상태 관리, 해시맵/세트 활용
def hard_sliding_window(s, k):
"""
예: 정확히 K개 고유 문자를 포함하는 최장 부분 문자열
"""
from collections import defaultdict
def at_most_k(k):
# K개 이하 고유 문자를 포함하는 최장 길이
char_count = defaultdict(int)
left = 0
max_len = 0
for right in range(len(s)):
char_count[s[right]] += 1
while len(char_count) > k:
char_count[s[left]] -= 1
if char_count[s[left]] == 0:
del char_count[s[left]]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
# 정확히 K개 = (K개 이하) - (K-1개 이하)
return at_most_k(k) - at_most_k(k - 1)
# 테스트
print(hard_sliding_window("eceba", 2)) # 3 ("ece")
핵심 포인트:
– 해시맵으로 빈도 관리
– “정확히 K” = “최대 K” – “최대 K-1” 변환 기법
– 원소 삭제 시 빈도 0 체크
| 난이도 | 윈도우 타입 | 자료구조 | 시간 복잡도 |
|---|---|---|---|
| 쉬움 | 고정 | 변수 | O(N) |
| 보통 | 가변 | 변수 + 투 포인터 | O(N) |
| 어려움 | 가변 | 해시맵/세트 | O(N) |
자주 하는 실수
1. 초기 윈도우를 잊어버림
# ❌ 잘못된 코드
def wrong(arr, k):
max_sum = 0 # 초기 윈도우 계산 누락!
for i in range(k, len(arr)):
# ...
# ✅ 올바른 코드
def correct(arr, k):
window_sum = sum(arr[:k]) # 초기 윈도우 설정
max_sum = window_sum
for i in range(k, len(arr)):
# ...
2. 윈도우 크기 검증 누락
# ❌ IndexError 위험
def wrong(arr, k):
return sum(arr[:k]) # len(arr) < k면 에러
# ✅ 엣지 케이스 처리
def correct(arr, k):
if len(arr) < k:
return None # 또는 0, [], 문제 조건에 맞게
return sum(arr[:k])
3. left 포인터 업데이트 실수
# ❌ 잘못된 left 이동
def wrong(s):
char_index = {}
left = 0
for right in range(len(s)):
if s[right] in char_index:
left = char_index[s[right]] + 1 # 뒤로 되돌아갈 수 있음!
# ✅ 단조 증가 보장
def correct(s):
char_index = {}
left = 0
for right in range(len(s)):
if s[right] in char_index:
left = max(left, char_index[s[right]] + 1) # 절대 감소하지 않음
4. while vs if 혼동
# ❌ 조건이 여러 번 위반될 수 있는데 if 사용
if current_sum >= target: # 한 번만 축소
left += 1
# ✅ 조건 만족까지 반복 축소
while current_sum >= target: # 완전히 만족할 때까지
current_sum -= arr[left]
left += 1
엣지 케이스 체크리스트
실전에서 반드시 확인해야 할 엣지 케이스:
- [ ] 빈 배열:
arr = [] - [ ] 윈도우 크기가 배열보다 큼:
len(arr) < k - [ ] 윈도우 크기가 1:
k = 1(특수 처리 불필요한지 확인) - [ ] 모든 원소가 같음:
[5, 5, 5, 5] - [ ] 음수 포함:
[-1, -2, -3](합계 문제에서 주의) - [ ] 조건을 만족하는 부분 배열이 없음:
min_len = inf반환 처리 - [ ] 전체 배열이 답:
left=0, right=n-1
# 엣지 케이스 테스트 예시
def test_edge_cases():
func = min_subarray_len
assert func(7, []) == 0 # 빈 배열
assert func(100, [1, 2, 3]) == 0 # 불가능
assert func(4, [1, 4, 4]) == 1 # 단일 원소
assert func(11, [1, 1, 1, 1, 1, 1, 1, 1]) == 11 # 전체 필요
assert func(15, [5, 1, 3, 5, 10, 7, 4, 9, 2, 8]) == 2 # [5,10]
print("All edge cases passed!")
변형 문제 및 응용
1. 문자열 패턴 매칭
def find_anagrams(s, p):
"""
LeetCode 438. Find All Anagrams in a String
문자열 s에서 p의 애너그램인 모든 부분 문자열의 시작 인덱스 찾기
"""
from collections import Counter
if len(p) > len(s):
return []
p_count = Counter(p)
window_count = Counter(s[:len(p)])
result = []
if window_count == p_count:
result.append(0)
for i in range(len(p), len(s)):
# 오른쪽 추가
window_count[s[i]] += 1
# 왼쪽 제거
window_count[s[i - len(p)]] -= 1
if window_count[s[i - len(p)]] == 0:
del window_count[s[i - len(p)]]
# 애너그램 체크
if window_count == p_count:
result.append(i - len(p) + 1)
return result
# 테스트
print(find_anagrams("cbaebabacd", "abc")) # [0, 6] ("cba", "bac")
2. 최대 K번 교체 문제
def longest_ones(nums, k):
"""
LeetCode 1004. Max Consecutive Ones III
최대 K개의 0을 1로 바꿀 수 있을 때, 최장 연속 1의 개수
"""
left = 0
zero_count = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
# 0이 K개 초과하면 왼쪽 축소
while zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
# 테스트
print(longest_ones([1,1,1,0,0,0,1,1,1,1,0], 2)) # 6
3. 과일 바구니 (고유 원소 제한)
def total_fruit(fruits):
"""
LeetCode 904. Fruit Into Baskets
최대 2종류 과일만 담을 수 있을 때, 연속으로 담을 수 있는 최대 개수
= 최대 2개 고유 원소를 포함하는 최장 부분 배열
"""
from collections import defaultdict
fruit_count = defaultdict(int)
left = 0
max_fruits = 0
for right in range(len(fruits)):
fruit_count[fruits[right]] += 1
# 3종류 이상이면 축소
while len(fruit_count) > 2:
fruit_count[fruits[left]] -= 1
if fruit_count[fruits[left]] == 0:
del fruit_count[fruits[left]]
left += 1
max_fruits = max(max_fruits, right - left + 1)
return max_fruits
# 테스트
print(total_fruit([1,2,1])) # 3
print(total_fruit([0,1,2,2])) # 3 ([1,2,2])
print(total_fruit([1,2,3,2,2])) # 4 ([2,3,2,2])
실전 팁
1. 문제 판별 체크리스트
슬라이딩 윈도우를 사용해야 하는지 빠르게 판별:
✅ "연속된", "부분 배열", "substring" 키워드
✅ "최대/최소 길이", "최장/최단"
✅ "크기 K인", "합이 S인"
✅ "중복 없는", "고유한 K개"
2. 코드 작성 순서
-
엣지 케이스 먼저 처리
python
if not arr or len(arr) < k:
return 0 -
초기 윈도우 설정
python
window = initialize(arr[:k]) -
슬라이딩 로직 구현
python
for i in range(k, n):
remove(arr[i-k])
add(arr[i]) -
결과 반환 전 검증
python
return result if result != initial_value else default
3. 디버깅 전략
def debug_sliding_window(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
# 디버깅 로그
print(f"Initial window: {arr[:k]}, sum={window_sum}")
for i in range(k, len(arr)):
removed = arr[i-k]
added = arr[i]
window_sum = window_sum - removed + added
# 각 단계 출력
print(f"Step {i-k+1}: Remove {removed}, Add {added}, Window sum={window_sum}")
max_sum = max(max_sum, window_sum)
return max_sum
4. 성능 최적화
| 최적화 기법 | 적용 상황 | 효과 |
|---|---|---|
| Early termination | 조건 만족 시 즉시 종료 | 평균 케이스 개선 |
| 비트 연산 | 문자 집합이 작을 때 | 해시맵 대신 비트마스크 |
| Deque 활용 | 윈도우 내 최대/최소값 추적 | O(N) 유지하며 min/max |
from collections import deque
def max_sliding_window(nums, k):
"""
LeetCode 239. Sliding Window Maximum
Deque로 윈도우 내 최대값을 O(1)에 추적
"""
dq = deque() # 인덱스 저장 (감소 순서 유지)
result = []
for i in range(len(nums)):
# 윈도우 범위 벗어난 인덱스 제거
if dq and dq[0] < i - k + 1:
dq.popleft()
# 현재 값보다 작은 값들 제거 (최대값 유지)
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# 윈도우가 완성되면 최대값 기록
if i >= k - 1:
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]
마무리
슬라이딩 윈도우는 연속된 부분 배열 문제를 O(N²)에서 O(N)으로 극적으로 최적화하는 강력한 패턴입니다. 핵심 포인트를 정리하면:
핵심 요약
- 적용 조건: 연속된 부분 배열/문자열, 최대/최소/합계 문제
- 두 가지 유형:
– 고정 크기: 크기 K가 정해진 경우 → 단순 슬라이딩
– 가변 크기: 조건에 따라 변경 → 투 포인터 활용 - 시간 복잡도: O(N) (중첩 루프처럼 보여도 분할 상환 분석 시 O(N))
- 공간 복잡도: O(1) ~ O(N) (해시맵 사용 여부)
- 필수 체크:
– 초기 윈도우 설정
– 엣지 케이스 (빈 배열, 크기 부족)
– left 포인터 단조 증가
– while vs if 올바른 선택
학습 로드맵
| 단계 | 문제 유형 | 추천 문제 |
|---|---|---|
| 1단계 | 고정 크기 기본 | LeetCode 643, 1456 |
| 2단계 | 가변 크기 기본 | LeetCode 209, 904 |
| 3단계 | 해시맵 활용 | LeetCode 3, 438, 567 |
| 4단계 | 고급 응용 | LeetCode 76, 239, 1004 |
다음 단계
슬라이딩 윈도우를 마스터했다면 다음 패턴으로 확장해보세요:
- 투 포인터(Two Pointers): 정렬된 배열에서 쌍 찾기
- 단조 스택/큐(Monotonic Stack/Queue): 윈도우 내 최대/최소값 추적
- 접두사 합(Prefix Sum): 구간 합 쿼리 최적화
슬라이딩 윈도우는 코딩 테스트 필수 패턴이며, 실무에서도 스트리밍 데이터 처리, 시계열 분석 등에 광범위하게 활용됩니다. 충분히 연습하여 자동으로 패턴이 떠오를 때까지 훈련하세요!
마지막 조언: 처음엔 Brute Force로 풀어본 후, 슬라이딩 윈도우로 최적화하는 연습을 하세요. 시간 복잡도 차이를 직접 체감하면 패턴이 더 확실히 이해됩니다.
Did you find this helpful?
☕ Buy me a coffee
Leave a Reply