슬라이딩 윈도우(Sliding Window) 기법 (개념, 차이점)

알고리즘 문제 해결, 특히 데이터 분석이나 네트워크 패킷 처리와 같이 연속된 데이터 스트림을 다루는 분야에서 성능 최적화는 필수적인 과제입니다. 특정 구간의 합계나 평균을 구하기 위해 매번 구간 내의 모든 값을 다시 계산하는 '브루트 포스(Brute Force)' 방식은 데이터의 크기가 커질수록 기하급수적으로 속도가 느려집니다. 이러한 비효율을 해결하기 위해 등장한 것이 바로 슬라이딩 윈도우(Sliding Window) 기법입니다. 창문을 옆으로 밀듯이 데이터 구간을 이동시키며 연산량을 획기적으로 줄이는 이 기술은 $O(N^2)$의 복잡도를 $O(N)$으로 최적화하는 핵심 알고리즘입니다.

1. 슬라이딩 윈도우(Sliding Window)의 핵심 개념

슬라이딩 윈도우는 배열이나 리스트와 같은 선형 자료구조에서 고정된 크기(혹은 가변 크기)의 '창(Window)'을 설정하고, 이 창을 한 칸씩 이동시키며 창 내부의 데이터를 분석하는 기법입니다. 이 알고리즘의 핵심은 '재사용'에 있습니다.

1-1. 중복 연산의 제거 원리

길이가 $N$인 배열에서 크기가 $K$인 부분 배열의 합을 구한다고 가정해 봅시다. 일반적인 방식은 각 시작점마다 $K$개의 요소를 모두 더해야 합니다. 하지만 슬라이딩 윈도우는 다릅니다.

초기화: 첫 번째 창(인덱스 $0$ ~ $K-1$)의 합을 계산합니다.
이동(Slide): 창을 한 칸 오른쪽으로 이동시킵니다.
최적화: 이때 모든 값을 다시 더하는 것이 아니라, 빠지는 값(맨 앞)을 빼고, 새로 들어오는 값(맨 뒤)을 더해줍니다.

즉, 이동할 때마다 단 두 번의 연산(+, -)만 수행하면 되므로, 윈도우 크기 $K$와 무관하게 항상 일정한 속도를 유지합니다.

2. 투 포인터(Two Pointers)와의 결정적 차이

많은 개발자가 투 포인터와 슬라이딩 윈도우를 혼동합니다. 두 기법 모두 구간을 탐색한다는 공통점이 있지만, '구간의 형태'와 '이동 방식'에서 명확한 차이가 있습니다.

2-1. 비교 분석

투 포인터: 구간의 크기가 수시로 변할 수 있으며, 두 포인터(Start, End)가 데이터의 상태에 따라 독립적으로 이동하거나 양 끝에서 좁혀오는 방식을 사용합니다. 주로 '두 수의 합'이나 '정렬된 배열' 문제에 쓰입니다.
슬라이딩 윈도우: 마치 창틀이 고정된 것처럼 두 포인터가 일정한 간격을 유지하며 동시에 이동하는 것이 기본입니다(고정 크기 윈도우의 경우). 주로 '연속된 구간'의 합, 평균, 최댓값 등을 구할 때 사용됩니다.

3. 파이썬(Python) 구현: 고정 크기 윈도우 최적화

다음은 배열에서 길이가 $K$인 연속 부분 배열 중, 합계가 가장 큰 값을 찾는 문제를 슬라이딩 윈도우로 해결한 코드입니다. 매번 합을 구하는 방식과 비교하여 연산 횟수가 얼마나 줄어드는지 주목하십시오.


def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1  # 배열 길이가 윈도우보다 작은 경우

    # 1. 첫 번째 윈도우의 합 계산 (초기값)
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # 2. 윈도우를 한 칸씩 슬라이딩하며 갱신
    # i는 새로 들어올 요소의 인덱스
    for i in range(k, n):
        # 핵심 로직: 기존 합 + (새로운 값 - 나가는 값)
        # arr[i]: 새로 들어오는 값 (Entrant)
        # arr[i-k]: 윈도우에서 빠지는 값 (Leaver)
        window_sum = window_sum + arr[i] - arr[i-k]
        
        # 최댓값 갱신
        max_sum = max(max_sum, window_sum)

    return max_sum

# 테스트 데이터
data = [2, 1, 5, 1, 3, 2]
k_size = 3

result = max_sum_subarray(data, k_size)
print(f"최대 구간 합: {result}") 
# 과정: [2,1,5]=8 -> [1,5,1]=7 -> [5,1,3]=9(최대) -> [1,3,2]=6

3-2. 가변 크기 슬라이딩 윈도우

윈도우 크기가 고정되지 않은 경우도 있습니다. 예를 들어 "합이 $S$ 이상이 되는 가장 짧은 구간"을 찾을 때는, 조건($S$ 이상)을 만족할 때까지 윈도우를 늘리다가(Expand), 조건을 만족하면 윈도우를 줄여가며(Shrink) 최소 길이를 찾습니다. 이 경우는 투 포인터 알고리즘의 성격과 혼합된 형태로 볼 수 있습니다.

[핵심 요약 : 슬라이딩 윈도우]
1. 원리: 겹치는 구간의 데이터를 재사용하여, 새로 들어오는 값과 나가는 값만 처리함으로써 연산량을 최소화합니다.
2. 효율성: 이중 반복문으로 인한 $O(N \times K)$의 복잡도를 $O(N)$ 선형 시간으로 단축시킵니다.
3. 활용: 네트워크 패킷 분석, 주가 이동 평균선 계산 등 연속된 데이터의 구간 통계 처리에 필수적입니다.

kguidebook0001 님의 블로그