슬라이딩 윈도우 기법

슬라이딩 윈도우 기법은 배열이나 리스트의 요소를 한정된 크기의 '윈도우'나 '서브리스트'로 나누어 분석할 때 사용되는 알고리즘 패턴입니다. 이 기법은 주로 부분 배열의 최대합, 최소값, 평균 등을 효율적으로 계산할 때 사용됩니다.

슬라이딩 윈도우의 기본 아이디어

슬라이딩 윈도우 기법의 핵심은 윈도우(부분 배열)가 데이터 구조를 통해 일정한 범위를 유지하며 입력 데이터를 순차적으로 스캔한다는 것입니다. 윈도우의 크기는 고정될 수도 있고 가변적일 수도 있으며, 윈도우가 한 위치에서 다음 위치로 이동할 때 일부 데이터는 윈도우에서 제외되고 새로운 데이터가 포함됩니다.

예시: 최대합 찾기

문제: 주어진 배열에서 크기가 **k**인 연속 부분 배열의 최대 합을 찾아라.

예를 들어, 배열 **arr = [1, -2, 3, 4, -1, 2, 1, -5, 4]**가 있고 **k=3**이라면, 우리는 최대 합을 가진 크기 3의 부분 배열을 찾아야 합니다.

슬라이딩 윈도우 알고리즘 적용

1. 초기 윈도우 설정: 첫 3개의 원소의 합을 계산합니다. 이 합을 **currentSum**으로 저장하고, 최대 합 **maxSum**도 이 값으로 초기화합니다.
   • currentSum = arr[0] + arr[1] + arr[2] = 1 - 2 + 3 = 2
   • maxSum = 2
2. 윈도우 슬라이딩: 윈도우를 한 칸씩 오른쪽으로 이동시키면서 합을 업데이트합니다. 이때, 윈도우에서 벗어나는 왼쪽의 원소는 빼고, 새로 포함되는 오른쪽의 원소는 더합니다.
   • 첫 번째 이동: currentSum = currentSum - arr[0] + arr[3] = 2 - 1 + 4 = 5, maxSum = max(maxSum, currentSum) = max(2, 5) = 5
   • 두 번째 이동: currentSum = currentSum - arr[1] + arr[4] = 5 - (-2) + (-1) = 6, maxSum = 6
   • 이후 계속 이동하면서 maxSum 업데이트...
3. 결과 반환: 모든 이동을 완료한 후, **maxSum**에는 최대 합이 저장됩니다.

코드 예제

function maxSum(arr, k) {
    let currentSum = 0;
    for (let i = 0; i < k; i++) {
        currentSum += arr[i];
    }
    let maxSum = currentSum;

    for (let i = k; i < arr.length; i++) {
        currentSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

const arr = [1, -2, 3, 4, -1, 2, 1, -5, 4];
console.log(maxSum(arr, 3));  // 결과 출력

이 알고리즘의 장점은 윈도우의 크기가 일정하게 유지되면서 데이터의 전체 스캔이 한 번만 필요하기 때문에, 시간 복잡도가 O(n)으로 매우 효율적입니다. 이처럼 슬라이딩 윈도우 기법은 다양한 문제에서 유용하게 활용될 수 있습니다.