[2026] 슬라이딩 윈도우 | 부분 배열 최적화 기법 완벽 정리

들어가며

연속 부분 배열이나 부분 문자열의 합·조건을 매번 처음부터 다시 계산하면 시간 초과가 나기 쉽습니다. 이 글에서는 윈도우를 한 칸씩 밀며 갱신하는 방식으로 복잡도를 줄이는 흐름을 단계적으로 익힐 수 있습니다.

”윈도우를 슬라이딩하며 최적화”

슬라이딩 윈도우는 연속된 부분 배열을 효율적으로 처리하는 기법입니다.

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

1. 고정 크기 윈도우

기본 패턴

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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. 가변 크기 윈도우

최소 길이 부분 배열

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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의 개수

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 최장 부분 문자열

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 애너그램 찾기

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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).

---

일상 비유로 이해하기: 시간 복잡도는 책에서 원하는 페이지를 찾는 방법으로 비유할 수 있습니다. O(1)은 목차를 보고 바로 찾기, O(log n)은 이진 탐색처럼 중간을 펼쳐 앞뒤 판단하기, O(n)은 첫 페이지부터 하나씩 넘기기, O(n²)은 모든 페이지 조합을 확인하기입니다.

윈도우 확장·축소 조건 패턴

1. 확장 (right++)
   항상 한 칸 넓혀서 현재 구간에 원소를 포함합니다. 고정 윈도우는 right만 순차 증가하고, 가변은 “조건을 만족시키기 위해” 넓힙니다.
2. 축소 (left++)
   • 고정 크기: right - left + 1 > k이면 왼쪽을 한 칸 당겨 길이 k 유지.
   • 가변 — 유효하지 않을 때: 예) 중복 문자, 0이 너무 많음, need 미충족이 아닌 “최소 길이” 찾기 전 단계 등.
   • 가변 — 유효한데 더 짧게 줄일 수 있을 때: Minimum Window에서 need 충족 후 left를 당겨 최소 길이 갱신.
3. 불변식(invariant)
   “윈도우가 만족해야 할 조건”을 한 문장으로 적어 두면, 언제 while로 left를 당길지가 명확해집니다. (예: “중복 문자가 없을 때까지 left 이동”.)

---

실전 팁

슬라이딩 윈도우 패턴

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 패턴 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()

---

정리

핵심 요약

1. 슬라이딩 윈도우: 연속 부분 배열 O(n) 처리
2. 고정 크기: 윈도우 크기 일정
3. 가변 크기: 조건에 따라 확장/축소
4. 최적화: O(n²) → O(n)

추천 문제

백준:

• 2003번: 수들의 합 2
• 21921번: 블로그 프로그래머스:
• 보석 쇼핑 LeetCode:
• 3. Longest Substring
• 438. Find All Anagrams

---

관련 글

• 그리디 알고리즘 |
• 알고리즘 시리즈 전체 목차
• 배열과 리스트
• 스택과 큐