[Algorithm] 슬라이딩 윈도우(Sliding Window)

 

슬라이딩 윈도우는 배열이나 문자열과 같은 선형 데이터 구조에서 특정 크기의 '윈도우'를 이동시키면서 문제를 해결하는 알고리즘 기법입니다. 이 방법은 다음과 같은 상황에서 특히 유용합니다:

• 연속된 요소들의 부분집합을 처리해야 할 때
• 배열이나 문자열에서 특정 조건을 만족하는 부분을 찾아야 할 때
• 고정된 크기의 윈도우를 이동시키면서 계산을 수행해야 할 때

 

슬라이딩 윈도우의 작동 원리

1. 윈도우 크기 설정: 문제에 따라 적절한 윈도우 크기를 정합니다.
2. 초기 윈도우 설정: 데이터 구조의 시작점에서 윈도우 크기만큼의 요소를 처리합니다.
3. 윈도우 이동: 윈도우를 한 칸씩 이동시킵니다.
4. 윈도우 업데이트: 새로 추가된 요소를 처리하고, 제외된 요소를 제거합니다.
5. 반복: 데이터 구조의 끝에 도달할 때까지 3-4 과정을 반복합니다.

 

슬라이딩 윈도우 예제: 연속된 K일 동안의 최대 매출 찾기

다음과 같은 문제를 생각해봅시다: "일별 매출 데이터가 주어졌을 때, 연속된 K일 동안의 최대 매출을 찾으시오."

 

Naive 접근법

먼저, 가장 단순한 방법을 살펴보겠습니다:

• 시간 복잡도: O(n*K)

function maxSalesNaive(sales, K) {
    let maxSales = 0;
    for (let i = 0; i <= sales.length - K; i++) {
        let windowSum = 0;
        for (let j = i; j < i + K; j++) {
            windowSum += sales[j];
        }
        maxSales = Math.max(maxSales, windowSum);
    }
    return maxSales;
}

해당 방법은 각 단계마다 처음부터 새로 계산하기 때문에 입력 크기가 증가할수록 성능이 저하될 가능성이 있습니다.

 

슬라이딩 윈도우 접근법

• 시간 복잡도: O(n)

function maxSalesSlidingWindow(sales, K) {
    if (K > sales.length) return null;

    let windowSum = 0;
    for (let i = 0; i < K; i++) {
        windowSum += sales[i];
    }

    let maxSales = windowSum;

    for (let i = K; i < sales.length; i++) {
        windowSum = windowSum - sales[i - K] + sales[i];
        maxSales = Math.max(maxSales, windowSum);
    }

    return maxSales;
}

 

슬라이딩 윈도우의 응용

• 문자열 처리: 가장 긴 중복 없는 부분 문자열 찾기
• 배열 처리: 특정 합을 가진 부분 배열 찾기
• 데이터 스트리밍: 실시간 데이터의 이동 평균 계산
• 네트워크: TCP의 흐름 제어