Previous
Next
슬라이딩 윈도우 | 부분 배열 최적화 기법 완벽 정리 | 핵심 개념과 실전 활용

슬라이딩 윈도우 | 부분 배열 최적화 기법 완벽 정리 | 핵심 개념과 실전 활용

· 42분 읽기 · 수정 중급 튜토리얼
슬라이딩 윈도우 | 부분 배열 최적화 기법 완벽 정리 | 핵심 개념과 실전 활용

이 글의 핵심

슬라이딩 윈도우는 연속 구간을 O(n)으로 다루는 기법입니다. 불변식으로 정당성을 밝히고, 고정·가변 예제를 넓힌 뒤 같은 방향 다중 포인터와 모노토닉 덱 최적화·상각 분석을 익히고, 관측·스트림·레이트 리밋 등 프로덕션 패턴까지 연결합니다.

시리즈 안내

#17 | 📋 전체 목차 | 이전: #16 투 포인터

들어가며

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

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

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

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

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

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)

고정 크기 추가 예제 1: 길이 k에서 모음의 최대 개수

길이가 정확히 k인 부분 문자열 중에서 모음(a,e,i,o,u) 개수의 최댓값을 구하는 문제는 전형적인 고정 윈도우입니다. 첫 k글자에서 모음 수를 세고, 한 칸씩 밀 때 나간 글자·들어온 글자만 반영하면 됩니다.

def max_vowels(s: str, k: int) -> int:
    vowels = set("aeiou")

    def is_vowel(c: str) -> bool:
        return c in vowels

    cur = sum(1 for c in s[:k] if is_vowel(c))
    best = cur
    for i in range(k, len(s)):
        cur += int(is_vowel(s[i])) - int(is_vowel(s[i - k]))
        best = max(best, cur)
    return best


print(max_vowels("leetcode", 3))  # 2 ("lee" 또는 "eet")

고정 크기 추가 예제 2: 길이 k 윈도우마다 “서로 다른 수”의 개수

정수 배열이 주어질 때, 길이 k인 각 연속 구간마다 서로 다른 값의 개수를 구하는 문제입니다. 슬라이딩하면서 collections.Counter(또는 defaultdict(int))로 빈도를 유지하고, 빈도가 0이 된 키는 제거해 유효한 distinct 개수만 추적합니다.

from collections import Counter

def distinct_numbers_in_windows(nums: list[int], k: int) -> list[int]:
    cnt = Counter(nums[:k])
    out = [len(cnt)]
    for i in range(k, len(nums)):
        left, right = nums[i - k], nums[i]
        cnt[left] -= 1
        if cnt[left] == 0:
            del cnt[left]
        cnt[right] += 1
        out.append(len(cnt))
    return out


print(distinct_numbers_in_windows([1, 2, 1, 3, 4, 3, 3, 2], 3))
# k=3 구간: [1,2,1]→2종, [2,1,3]→3종, [1,3,4]→3종, ...

실무 메모: 윈도우 안 원소 종류가 많지 않다면 크기 σ짜리 배열로 빈도를 두는 편이 더 빠를 수 있습니다. 반대로 값의 범위가 크면 해시 기반 카운터가 안전합니다.

고정 크기 추가 예제 3: 최대 평균와 “합 동치”

LeetCode 643. Maximum Average Subarray I처럼 길이 k 부분 배열의 평균 최댓값은, k가 고정이면 합이 최대인 구간과 동치입니다. 나눗셈은 마지막에 한 번만 하면 되어 수치 안정성·비용 측면에서도 합을 유지하는 편이 낫습니다.

def find_max_average(nums: list[int], k: int) -> float:
    window_sum = sum(nums[:k])
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
    return best / k

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

가변 크기 추가 예제 1: 합이 target 이하인 최장 부분 배열 (비음수)

원소가 모두 0 이상일 때, 부분합이 target을 넘지 않도록 하면서 길이를 최대화하는 문제는 “right로 확장하다가 초과하면 left로 축소” 패턴이 정답입니다. 음수가 섞이면 접두합 + 해시맵 등 다른 모델이 필요하므로, 조건(비음수)을 먼저 확인하는 것이 안전합니다.

def longest_subarray_at_most_sum(nums: list[int], target: int) -> int:
    left = 0
    s = 0
    best = 0
    for right, x in enumerate(nums):
        s += x
        while s > target and left <= right:
            s -= nums[left]
            left += 1
        best = max(best, right - left + 1)
    return best


print(longest_subarray_at_most_sum([1, 2, 3, 4, 5], 8))  # 3 ([1,2,3])

가변 크기 추가 예제 2: 서로 다른 문자가 최대 K개인 최장 부분 문자열

LeetCode 340. Longest Substring with At Most K Distinct Characters류 문제입니다. right로 문자를 추가하고, distinct 개수가 K를 초과할 때까지 left를 당깁니다. 빈도 맵에서 0이 된 문자는 키에서 제거해 distinct 수를 O(1)에 가깝게 유지합니다.

def length_longest_substring_k_distinct(s: str, k: int) -> int:
    from collections import defaultdict

    freq = defaultdict(int)
    distinct = 0
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if freq[ch] == 0:
            distinct += 1
        freq[ch] += 1
        while distinct > k:
            c = s[left]
            freq[c] -= 1
            if freq[c] == 0:
                distinct -= 1
            left += 1
        best = max(best, right - left + 1)
    return best


print(length_longest_substring_k_distinct("eceba", 2))  # 3 ("ece")

가변 크기 추가 예제 3: “길이 제한 없이” 조건만 만족하는 최소·최장

  • 최소 길이(합 ≥ target, need 충족 등): 조건을 만족한 뒤 left를 당겨 불필요하게 긴 구간을 줄입니다.
  • 최대 길이(0의 개수 ≤ k, distinct ≤ K 등): 조건이 깨질 때까지 left를 당겨 유효 구간만 남깁니다.

두 경우 모두 “right는 한 번씩만 증가”하고 “left는 필요한 만큼만 전진”하므로, 내부 while이 있어도 상각 O(n)인 점은 동일합니다.

슬라이딩 윈도우의 불변식과 정당성

슬라이딩 윈도우가 “맞는” 이유는, 매 스텝에서 유지하려는 논리 조건(불변식, invariant)을 명시할 수 있고, 그 불변식이 left·right의 단조 전진과 맞물리기 때문입니다. 아래는 대표적인 두 유형에 대한 정당성 스케치입니다.

상태와 불변식

연속 구간 [L, R]를 윈도우라 하면, 알고리즘은 매 순간 정수 쌍 (L, R)과 그에 딸린 집계값(합, 카운트, 빈도 맵 등)을 유지합니다. 핵심은 다음 두 가지입니다.

  1. 탐색 공간: 답이 되는 모든 후보 구간은 어떤 R을 “오른쪽 끝”으로 갖습니다. 우리는 R을 0부터 n−1까지 한 번씩만 증가시키며 지나갑니다.
  2. 단조성: L과 R은 감소하지 않습니다. 즉, 이미 버린 왼쪽 원소를 다시 삼키지 않습니다.

이 두 가지가 성립하면, “같은 (L, R)를 두 번 이상 본다”는 낭비를 피하는 설계가 가능해집니다.

고정 길이 k에 대한 불변식

불변식 I_fixed
처리 시점에서 R이 최소 k−1 이상일 때, 항상 R − L + 1 = k이고, 윈도우에 포함된 원소는 정확히 A[R−k+1 … R]입니다.

갱신
R을 1 증가시킨 직후에는 길이가 k+1이 되므로, 한 번 L을 1 증가시켜 다시 길이 k로 맞춥니다. 이는 “새 원소를 넣고 가장 오래된 원소를 낸다”는 한 스텝의 의미적 갱신과 같습니다.

정당성(스케치)
길이 k인 모든 구간은 고유한 오른쪽 끝 R을 갖고, 알고리즘은 각 R ≥ k−1에 대해 정확히 한 번 그 구간을 대표합니다. 따라서 최대·최소·합 등 구간 집계의 전역 최적해를 빠뜨리지 않습니다.

가변 길이(합이 target 이상인 최소 길이)에 대한 불변식

위 min_subarray_len에서 내부 while이 끝난 직후를 보면, 다음이 성립합니다.

불변식 I_var
각 고정된 right에 대해, 루프 종료 후에는 current_sum < target이거나 left == right + 1입니다. 즉, “left를 더 당기면 조건을 만족하는 더 짧은 후보가 있다”는 가능성은 남기지 않고 당깁니다.

직관적으로, right를 늘리기 전에 가능한 한 left를 오른쪽으로 밀어 길이를 줄입니다. 이때 각 right마다 남는 left는 “[left, right]가 조건을 만족하는 가장 짧은(가장 오른쪽으로 당긴) 왼쪽 끝”에 해당하는 경우가 많습니다(문제 조건에 따라 “최소 길이” 증명 문구는 약간 달라질 수 있으나, 불필요하게 넓은 윈도우를 끌고 가지 않는다는 구조는 동일합니다).

최적해를 놓치지 않는 이유(스케치)

길이를 최소화하는 유형에서, 임의의 최적 구간 S* = [L*, R*]를 택합시다. 알고리즘이 R = R에 도달했을 때, current_sum이 target 이상이면 내부 while이 left를 L 이상으로 밀어 최소 길이 후보를 갱신합니다. current_sum이 아직 부족하면 R을 더 키워야 하므로, 그 경우는 아직 R*에 도달하지 않은 단계입니다. 즉, 각 오른쪽 끝에 대해 “조건을 만족하는 가장 좋은 왼쪽 끝”을 탐욕적으로 고정하는 형태가, 문제가 요구하는 목적 함수(예: 최소 길이)와 맞물릴 때 정답 전략이 됩니다. (문제마다 “탐욕이 맞는” 이유가 다르므로, 시험에서는 목적 함수·조건을 한 줄 불변식으로 적은 뒤 스케치를 맞추는 습관이 안전합니다.)

고정 크기 vs 가변 크기 윈도우

구분고정 크기가변 크기
윈도우 길이k 등으로 항상 동일조건(합, 중복, 카운트)에 따라 늘었다 줄었다
전형적 루프right만 전진하고, right - left + 1 == k일 때 한 칸씩 left도 전진right로 확장하고, 조건 깨질 때까지 left로 축소
대표 문제크기 k인 부분 배열 합·최댓값, 고정 길이 애너그램최소 길이 부분합, 중복 없는 최장 부분 문자열, 최소 윈도우 부분 문자열
투 포인터와left = right - k + 1로도 표현 가능아래 “확장·축소 패턴”과 동일한 두 포인터 사고

둘 다 left, right가 앞으로만 가는 “같은 방향 두 포인터”이며, 차이는 길이가 고정인지입니다.

패턴 수준에서의 구분(설계 메모)

  • 고정 윈도우는 “한 스텝에 들어온 것·나간 것”만 갱신하는 차분 업데이트(delta) 문제로 정리하기 쉽습니다. 길이가 일정하므로, 집계량(합, XOR, 다항 해시, 빈도 벡터)을 유지할 때 불필요한 재계산이 사라집니다.
  • 가변 윈도우는 보통 유효성 함수 valid(L, R)를 정의하고, “right로 유효해질 때까지 확장 → 유효성을 깨뜨리지 않는 한 left를 당김” 또는 그 반대의 확장·축소 규칙으로 씁니다. 여기서 valid가 무엇인지(중복 없음, 0의 개수 ≤ k, need 충족 등)가 곧 구현의 전부입니다.

상태 기계 관점(고정 vs 가변)

고정 길이에서는 매 스텝이 “크기 k 유지”라는 단일 모드에 가깝습니다. 가변 길이에서는 스텝마다 확장 모드와 축소 모드가 번갈아 나타나며, 문제는 “축소를 언제 멈출지” 한 줄로 귀결되는 경우가 많습니다. 이 한 줄이 앞 절의 불변식 I_var와 정확히 대응합니다.

같은 방향 다중 포인터(투 포인터)와 슬라이딩 윈도우

슬라이딩 윈도우는 구현상 거의 항상 left와 right(또는 i, j) 두 개의 인덱스를 씁니다. 교재에 따라 이를 “투 포인터”라 부르기도 하고, “슬라이딩 윈도우”라 부르기도 합니다. 혼란을 줄이려면 배열의 방향으로 구분하는 편이 좋습니다.

양 끝 투 포인터 vs 같은 방향 두 포인터

구분전형적 조건이동
양 끝정렬 배열에서 합·곱 목표, 팰린드롬 판정 등left++, right--로 구간을 좁힘
같은 방향연속 부분 배열/문자열, 고정·가변 윈도우left, right가 모두 오른쪽으로만 진행

같은 방향 패턴은 알고리즘 시리즈 16 — 투 포인터와 연결해 읽으면, “정렬된 입력에서의 양 끝”과 “연속 구간에서의 한 방향”을 문제 유형별로 나누기 쉽습니다.

for right + while left의 역할 분담

  • right(외곽 루프): 새 원소를 항상 한 번씩 윈도우에 포함시키며 전체 배열을 한 번 순회합니다.
  • left(내부 while): 윈도우가 문제의 유효 조건을 위반하지 않도록 왼쪽을 당깁니다. “고정 길이 k 유지”, “중복 제거”, “0의 개수 ≤ k”, “need 충족 후 최소 길이” 등이 여기에 해당합니다.

핵심 관찰: left가 되돌아가지 않으면, left가 증가하는 총 횟수는 n을 넘지 않습니다. 그래서 겉보기 이중 루프여도 선형 시간이 됩니다.

삼중 루프가 되는 경우(주의)

아래는 의도적으로 나쁜 예입니다. left를 매번 0으로 되돌리면 연속 구간을 체계적으로 밀지 못하고 O(n²)이 됩니다.

# 나쁜 예: left를 매번 처음부터 재탐색 (브루트 포스에 가깝다)
def bad(nums, k):
    best = 0
    for right in range(len(nums)):
        left = 0  # 매번 리셋 — 슬라이딩 윈도우가 아님
        s = 0
        for j in range(left, right + 1):
            s += nums[j]
        # ...
    return best

같은 방향 두 포인터로 바꾸면 left는 이전 스텝의 값에서 이어서만 움직입니다.

“다중 포인터”라는 표현이 쓰이는 경우

  • 두 개의 배열을 동시에 한 방향으로 진행하며 병합·교집합을 만드는 패턴(예: 정렬된 두 배열의 공통 원소)은 인덱스가 두 쌍일 뿐, 연속 윈도우와는 목적이 다릅니다.
  • 세 포인터(예: 정렬 배열에서 세 수의 합 0)는 보통 정렬 + 양 끝 + 중간 조합입니다. 슬라이딩 윈도우와는 문제 클래스가 다릅니다.

이 글에서 말하는 “다중 포인터”는 연속 구간을 표현하는 left/right 한 쌍에 집중하면 됩니다. 구현할 때는 변수 이름만 l/r, i/j로 바꿔도 불변식과 단조 전진만 지키면 동일한 기법입니다.

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/coverright로 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 카운트로 조건 충족”을 강조한 최소 예입니다.)

단조 큐(모노토닉 덱)로 구간 최댓값·최솟값

고정 길이 k 윈도우의 최댓값을 매 위치에서 구해야 할 때, 매번 윈도우 안을 훑으면 O(k)가 곱해져 O(nk)가 됩니다. 여기서 단조 큐(모노토닉 deque)를 쓰면 원소마다 “언제까지 후보로 남을지”를 정리해 두어, 전체 O(n)로 끝낼 수 있습니다.

아이디어

덱에 인덱스를 넣되, 대응 값이 감소(최댓값 후보) 또는 증가(최솟값 후보)하도록 유지합니다. 새 값이 들어오면, 뒤에서부터 “나보다 약한 후보는 앞으로도 절대 최댓값이 될 수 없다”는 이유로 제거합니다. 윈도우에서 빠지는 인덱스는 앞에서 제거합니다.

이 구조의 본질은 후보 집합의 누적 지배(domination)입니다. 더 새롭고 더 큰 값이 들어오면, 더 오래되고 더 작은 값은 구간 최댓값 경쟁에서 영구히 탈락합니다.

예제: 슬라이딩 윈도우 최댓값

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """
    길이 k인 각 연속 구간의 최댓값을 왼쪽부터 반환합니다.
    덱에는 인덱스를 저장하며, nums[덱의 값]은 감소(비증가) 순서를 유지합니다.
    """
    dq = deque()  # 인덱스 저장, nums[dq[0]]가 현재 윈도우 최댓값 후보
    out = []

    for i, x in enumerate(nums):
        # i를 넣기 전, 뒤에서부터 나보다 작은 인덱스는 제거(지배됨)
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)

        # 윈도우 왼쪽이 밀려 dq[0]이 범위 밖이면 제거
        if dq[0] <= i - k:
            dq.popleft()

        # 길이 k가 된 뒤부터 출력
        if i >= k - 1:
            out.append(nums[dq[0]])

    return out


# 예: [1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))

최솟값이 필요하면 비교 연산을 <= 대신 >=로 바꿔 “증가 단조”를 유지하면 됩니다.

최솟값 슬라이딩 윈도우(모노토닉 증가 덱)

최댓값용 덱은 nums[dq[-1]] <= x일 때 뒤에서 pop하여 감소(비증가) 순서를 유지했습니다. 최솟값은 대칭으로, 뒤에서부터 nums[dq[-1]] >= x인 인덱스를 제거해 증가(비감소) 순서를 유지하면 됩니다. 윈도우 밖 인덱스 제거(dq[0] <= i - k)는 동일합니다.

from collections import deque

def min_sliding_window(nums: list[int], k: int) -> list[int]:
    dq = deque()
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] >= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out


print(min_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))  # [-1,-3,-3,-3,3,3]

최댓값과 최솟값을 동시에 (두 덱 또는 한 스캔)

구간마다 최댓값과 최솟값의 차이 같은 집계가 필요하면, 덱을 두 개 두고 같은 인덱스 i에 대해 동시에 유지하면 됩니다. 각 덱 연산은 여전히 원소당 상각 O(1)이므로 전체는 O(n)입니다. (같은 i에서 앞 원소가 빠질 때 두 덱 모두에서 popleft 가능한지 확인합니다.)

주의: “덱에 값만 넣기”보다 인덱스를 넣고 nums[i]로 비교하는 편이 윈도우 경계 처리에 안전합니다. 값이 같을 때는 인덱스가 작은 것이 먼저 나가도록 tie-break 규칙을 정하면, 구현 실수로 빈 덱을 참조하는 경우를 줄일 수 있습니다.

다른 최적화와의 비교

  • 합·XOR·가변 길이 빈도: 보통 차분 갱신(나간 원소 빼기, 들어온 원소 더하기)으로 충분합니다. 덱은 “구간 최댓/최소”처럼 비가역적 집계에 쓰입니다.
  • 세그먼트 트리 / Sparse Table: 정적 배열의 임의 구간 질의에는 강하지만, 슬라이딩이 한 칸씩만 이동한다면 모노토닉 덱이 더 단순하고 O(n)입니다.
  • 우선순위 큐(힙): 최댓값을 꺼낼 수 있으나, “윈도우 밖 원소”를 지연 삭제하려면 lazy deletion이 필요해 구현이 무거워질 수 있습니다. 고정 슬라이딩에는 덱이 흔히 더 깔끔합니다.

복잡도(덱 연산의 상각)

각 인덱스는 덱에 최대 한 번 push되고, 최대 한 번 pop됩니다(앞/뒤 제거 포함). 따라서 전체 덱 연산 수는 O(n)이고, 출력은 O(n−k+1)입니다. 합쳐서 O(n)입니다.

시간 복잡도 분석

  • 브루트 포스
    모든 연속 구간 [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(n)인가)

코드에 for right 바깥에 while left ...가 있으면, 겉보기에는 O(n²)처럼 느껴집니다. 그러나 포인터 단조성이 있으면 달라집니다.

명제
left와 right가 각각 0에서 시작해 최대 n−1까지 감소 없이 증가만 한다면, 전체 알고리즘에서 수행되는

  • left += 1의 총 횟수 ≤ n
  • right += 1의 총 횟수 ≤ n

가 성립합니다(보통 for가 right를 담당).

증명 스케치
left는 매번 1씩만 증가하고 범위 [0, n−1] 안에 머뭅니다. 한 번 커진 left는 다시 작아지지 않으므로, 증가 횟수는 n을 넘을 수 없습니다. 따라서 내부 while이 도는 총합은 “left가 전진하는 총거리”로 상한이 잡히고, 이는 O(n)입니다. 바깥 for right도 O(n)이므로, 두 포인터 합작업은 O(n)입니다.

다른 관점(계정·상각)
각 원소는 “right가 지나가며 들어올 때 한 번”, “left가 지나가며 나갈 때 한 번”만 윈도우에 관여합니다. 집계 자료구조가 O(1)에 가깝게 갱신된다면, 원소당 O(1) 상각으로 전체가 O(n)입니다.

주의
left가 되돌아가거나(예: 일부 최적화 실패), 집계 갱신이 윈도우 길이에 비례하면 선형이 깨질 수 있습니다. 문제마다 불변식 + 단조성을 확인해야 합니다.

일상 비유로 이해하기: 시간 복잡도는 책에서 원하는 페이지를 찾는 방법으로 비유할 수 있습니다. 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 이동”.)

실전 팁

슬라이딩 윈도우 패턴

# 패턴 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(1)에 가깝게 갱신”이라는 골격은 동일합니다.

관측·메트릭: 롤링 윈도우

  • 고정 구간 평균·합: 최근 k분·k개 요청의 합·평균(이동 평균)은 고정 길이 슬라이딩 윈도우의 전형입니다. 새 샘플이 들어오면 가장 오래된 샘플을 제거하는 순환 버퍼(ring buffer)와 한 쌍으로 구현합니다.
  • 분위수·중앙값: 단순 합과 달리 순서 통계는 덱만으로 부족하고, 히스토그램·스케치(예: t-digest) 등 별도 구조가 필요합니다. “윈도우”라는 틀은 같아도 집계 자료구조 난이도는 문제마다 다릅니다.

로그·이벤트 처리

  • 윈도우 집계: 스트림 처리(예: Flink, Kafka Streams)에서 슬라이딩 윈도우(sliding window)와 텀블링 윈도우(tumbling window)는 시간축을 잘라 집계합니다. 알고리즘 교과서의 “고정 k”와 같이 경계 길이가 명확한 경우가 많고, 지연·워터마크 이슈는 불변식이 깨지는 예외 상황(늦게 도착한 이벤트)을 다루는 쪽에 가깝습니다.
  • 중복 제거·세션: “같은 사용자의 마지막 T초 안 이벤트만 유효” 같은 규칙은, 키별로 만료 시각을 두고 큐에서 밀어내는 패턴으로 연결할 수 있습니다(자료구조는 deque·우선순위 큐 등).

네트워크·제어

  • TCP 슬라이딩 윈도우: 신뢰 있는 전송에서 “아직 ACK 안 난 바이트 수”를 제한해 혼잡을 조절합니다. 윈도우 크기가 동적으로 변한다는 점에서 교과서의 가변 윈도우와 비유할 수 있으나, 목적은 최적 부분배열이 아니라 전송 제어입니다.
  • 속도 제한(rate limiting): 토큰 버킷·누출 버킷은 “시간창 안 허용량”을 유지한다는 점에서 시간축 슬라이딩과 사고가 맞닿습니다.

API·신뢰성(프로덕션에서 자주 보는 “창”)

  • 고정 윈도우 레이트 리밋: “최근 1분에 N회까지”처럼 경계가 고정된 시간창은 구현상 순환 버퍼에 타임스탬프를 넣고, 만료된 요소를 앞에서 제거하는 고정 길이·시간 기반 슬라이딩과 같습니다. Redis ZSET + ZRANGEBYSCORE로 오래된 항목을 잘라 내는 패턴도 같은 골격입니다.
  • 슬라이딩 윈도우 vs 토큰 버킷: 슬라이딩은 “지난 T초의 요청 수”에 가깝고, 토큰 버킷은 누적 허용량이 일정 속도로 충전되는 모델입니다. 트래픽 형태에 따라 버스트 허용 여부가 달라 SLO를 맞추는 정책 선택이 달라집니다.
  • 서킷 브레이커의 오류 창: 연속 실패·최근 실패 비율을 짧은 시간창에서 보고 상태를 OPEN/HALF-OPEN으로 바꿉니다. “윈도우 안에서 실패 카운트”는 코딩 테스트의 고정·가변 카운트 윈도우와 같은 상태 집계입니다.
  • 에러 버짓·SLO: 한 달 허용 장애 시간을 작은 창으로 쪼개 관리할 때도 “남은 예산”을 롤링으로 추적하는 사고가 유용합니다(정책은 조직마다 다름).

데이터 파이프라인·품질

  • 지연·중복 이벤트: 스트림에서 “윈도우”는 이론상 깔끔하지만, 실제로는 늦게 도착한 레코드가 윈도우 경계를 흔듭니다. 코딩 테스트의 배열 인덱스와 달리, 운영에서는 워터마크·allowed lateness가 불변식을 보완합니다.
  • 세션 윈도우: 사용자 활동이 끊기면 세션을 닫는 갭 타임아웃은 “연속 구간을 끊는 조건”이 바뀐 형태의 가변 윈도우에 가깝습니다.

실무에서의 체크리스트

  1. 윈도우가 “연속 구간”인가? 끊기면 슬라이딩이 아니라 다른 모델(그래프, DP)일 수 있습니다.
  2. 집계가 가역적인가(빼기 가능)? 합·카운트는 쉽고, 최솟값·중앙값은 보조 자료구조가 필요합니다(모노토닉 덱, 두 힙 등).
  3. 시간이 실시간인가 배열 인덱스인가? 후자는 코딩 테스트, 전자는 운영 이슈(지연·중복·드롭)까지 포함합니다.

정리

핵심 요약

  1. 슬라이딩 윈도우: 연속 부분 배열을 한 칸씩 밀며 집계를 갱신해 O(n)로 처리합니다.
  2. 불변식·정당성: 고정 길이 k는 “항상 길이 k”, 가변 길이는 “while 종료 후 조건이 깨지지 않도록 left를 최대한 당김” 등으로 스케치할 수 있습니다.
  3. 고정 vs 가변: 고정은 차분 갱신(합·모음·distinct 카운트 등), 가변은 유효성 함수와 확장·축소 규칙으로 설계합니다.
  4. 같은 방향 두 포인터: for right와 while left의 역할을 분리하고, left를 리셋하지 않는 것이 선형 시간의 전제입니다.
  5. 모노토닉 덱: 구간 최댓값·최솟값을 후보 정리로 원소당 상각 O(1)에 가깝게 유지합니다. 최대·최소 동시 집계는 덱 두 개로 같은 스캔을 공유할 수 있습니다.
  6. 상각 분석: left·right가 되돌아가지 않으면 이중 루프 형태도 합쳐서 O(n)인 경우가 많습니다.
  7. 프로덕션: 롤링 메트릭, 스트림·세션 윈도우, 고정창 레이트 리밋, 서킷 브레이커·SLO 창 등에서 같은 “경계 밀기” 사고가 반복됩니다.
  8. 최적화: 이중 구간 나열 O(n²)~O(n³) 대비, 적절한 윈도우·자료구조로 O(n) 또는 O(n log n)까지 낮출 수 있습니다.

추천 문제

백준:

관련 글

심화 부록: 구현·운영 관점

이 부록은 앞선 본문에서 다룬 주제(「슬라이딩 윈도우 | 부분 배열 최적화 기법 완벽 정리」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.

내부 동작과 핵심 메커니즘

flowchart TD
  A[입력·요청·이벤트] --> B[파싱·검증·디코딩]
  B --> C[핵심 연산·상태 전이]
  C --> D[부작용: I/O·네트워크·동시성]
  D --> E[결과·관측·저장]
sequenceDiagram
  participant C as 클라이언트/호출자
  participant B as 경계(런타임·게이트웨이·프로세스)
  participant D as 의존성(API·DB·큐·파일)
  C->>B: 요청/이벤트
  B->>D: 조회·쓰기·RPC
  D-->>B: 지연·부분 실패·재시도 가능
  B-->>C: 응답 또는 오류(코드·상관 ID)
  • 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
  • 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
  • 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
  • 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.

프로덕션 운영 패턴

영역운영 관점 질문
관측성요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가
안전성입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가
신뢰성재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가
성능캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가
배포롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가
용량피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가

스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.

확장 예시: 엔드투엔드 미니 시나리오

앞선 본문 주제(「슬라이딩 윈도우 | 부분 배열 최적화 기법 완벽 정리」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

  1. 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
  2. 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
  3. 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
  4. 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
  5. 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.
handle(request):
  ctx = newCorrelationId()
  validated = validateSchema(request)
  authorize(validated, ctx)
  result = domainCore(validated)
  persistOrEmit(result, idempotentKey)
  recordMetrics(ctx, latency, outcome)
  return result

문제 해결(Troubleshooting)

증상가능 원인조치
간헐적 실패레이스, 타임아웃, 외부 의존성, DNS최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검
성능 저하N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거
메모리 증가캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납상한·TTL·힙/FD 스냅샷 비교
빌드·배포만 실패환경 변수, 권한, 플랫폼 차이, lockfileCI 로그와 로컬 diff, 런타임·이미지 버전 핀
설정 불일치프로필·시크릿·기본값, 리전스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화
데이터 불일치비멱등 재시도, 부분 쓰기, 캐시 무효화 누락멱등 키·아웃박스·트랜잭션 경계 재검토

권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.

배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 슬라이딩 윈도우는 연속 구간을 O(n)으로 다루는 기법입니다. 고정·가변 예제, 같은 방향 다중 포인터, 모노토닉 덱, 상각 분석, 관측·스트림 실무 패턴을 정리합니다. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

이 글에서 다루는 키워드 (관련 검색어)

알고리즘, 슬라이딩윈도우, Sliding Window, 최적화, 코딩테스트 등으로 검색하시면 이 글이 도움이 됩니다.