슬라이딩 윈도우 알고리즘: 고정 구간 탐색의 최적화 기법

네트워크를 통해 들어오는 데이터 스트림이나 시계열 데이터에서 '최근 7일간의 매출 합계' 또는 '길이가 K인 구간의 최대 이익' 등을 구해야 할 때가 있습니다. 구간의 크기가 고정되어 있음에도 불구하고, 매번 새로운 구간의 모든 원소를 다시 더하는 것은 극심한 낭비입니다. 이때 마치 창문을 옆으로 미는 것처럼, 공통된 부분은 유지하고 양 끝의 데이터만 갱신하는 슬라이딩 윈도우(Sliding Window) 기법은 최적의 해법이 됩니다. 본 포스팅에서는 슬라이딩 윈도우의 매커니즘과 투 포인터와의 차이점을 2,500자 이상의 전문적인 기술 분석으로 정리해 드립니다.

1. 슬라이딩 윈도우의 작동 원리: 재사용의 지혜

슬라이딩 윈도우의 핵심은 '중복 계산의 제거'에 있습니다. 예를 들어 크기가 3인 윈도우가 한 칸 옆으로 이동한다고 가정해봅시다. 이때 윈도우에 포함된 3개의 숫자 중 2개는 이전 상태와 동일합니다. 따라서 새로운 윈도우의 합을 구할 때 3개를 모두 다시 더할 필요 없이, 새로 들어온 숫자를 더하고 나간 숫자를 빼기만 하면 됩니다. 이 단순한 원리가 데이터가 방대해질수록 상상 이상의 성능 차이를 만들어냅니다.

1-1. 시간 복잡도의 비약적 단축

전체 배열의 크기가 $N$, 윈도우의 크기가 $K$일 때, 매번 새로 계산하면 $O(N \times K)$가 소요됩니다. 하지만 슬라이딩 윈도우 기법을 적용하면 윈도우 이동 시마다 단 두 번의 연산(덧셈 하나, 뺄셈 하나)만 발생하므로 전체 복잡도는 $O(N)$으로 고정됩니다. $K$가 커질수록 이 기법의 가치는 기하급수적으로 상승합니다.

2. 슬라이딩 윈도우 vs 투 포인터: 결정적 차이

두 기법 모두 배열의 구간을 다룬다는 공통점 때문에 혼동하기 쉽지만, 명확한 차이점이 존재합니다.

슬라이딩 윈도우: 구간(창문)의 너비가 고정(Fixed)되어 있습니다. 주로 '고정된 길이' 내에서의 특징을 찾을 때 사용합니다.
투 포인터: 구간의 너비가 조건에 따라 가변(Variable)적으로 변합니다. 주로 '조건을 만족하는 구간'의 길이나 개수를 찾을 때 사용합니다.

이 두 기법은 서로 보완적인 관계에 있으며, 문제의 요구사항이 '고정된 구간'인지 '유동적인 구간'인지를 파악하는 것이 알고리즘 선택의 핵심입니다.

3. 고급 응용: 슬라이딩 윈도우와 덱(Deque)

단순한 구간 합을 넘어 '구간 내의 최댓값/최솟값'을 구해야 할 때는 덱(Deque) 자료구조를 결합합니다. 덱을 사용하여 윈도우 안에서 최솟값의 후보가 될 가능성이 있는 인덱스들만 유지함으로써, $O(N)$ 만에 모든 윈도우의 최솟값을 찾아낼 수 있습니다. 이는 최첨단 금융 트레이딩 시스템의 이동평균선 계산이나 실시간 신호 처리에서 매우 중요하게 다루어지는 최적화 테크닉입니다.

4. 실무에서의 슬라이딩 윈도우 활용 사례

슬라이딩 윈도우는 전산학 전반에 걸쳐 광범위하게 응용되고 있습니다.

TCP 흐름 제어: 네트워크 패킷 전송 시 수신 측의 버퍼 크기에 맞춰 전송량을 조절하는 '슬라이딩 윈도우 프로토콜'.
데이터 스트리밍: 실시간으로 유입되는 데이터에서 최근 1시간 동안의 평균 온도나 주가 변동 탐지.
문자열 매칭: DNA 서열에서 특정 길이의 유전자 패턴이 나타나는 빈도 분석.
오디오 처리: 소리 데이터를 짧은 프레임 단위로 나누어 특징(Pitch, Timbre)을 추출하는 FFT(고속 푸리에 변환) 전처리.


# 고정 크기 k인 윈도우의 최대 합 구하기 (Python)
def max_window_sum(arr, k):
    if len(arr) < k: return 0
    
    # 1. 초기 윈도우 합 계산
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # 2. 슬라이딩 윈도우 이동
    for i in range(len(arr) - k):
        # 나가는 원소 빼고 들어오는 원소 더하기
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
        
    return max_sum

[슬라이딩 윈도우 핵심 요약]
1. 전략: 고정된 크기의 구간을 이동시키며 양 끝의 변화만 반영하여 효율성을 극대화합니다.
2. 성능: 불필요한 반복 계산을 제거하여 $O(N \times K)$의 문제를 $O(N)$으로 해결합니다.
3. 구분: 투 포인터와 달리 구간의 너비가 일정하다는 점이 특징이며, 실시간 데이터 분석에 필수적입니다.

tech-korea