슬라이딩 윈도우 (Sliding Window)

슬라이딩 윈도우 (Sliding Window) 설명:

슬라이딩 윈도우는 연속적인 데이터(일반적으로 배열이나 리스트)에서 고정된 크기의 연속적인 부분 집합을 탐색하거나 가변 크기의 연속적인 부분 집합을 탐색하는데 사용되는 알고리즘 패턴입니다. 슬라이딩 윈도우는 효과적으로 크기가 큰 데이터에서 연속적인 부분 집합 문제를 해결할 수 있게 해줍니다.

이 기법은 주로 연속된 데이터 구간에서 최대값, 최소값, 합계 등을 빠르게 계산하는 데 사용됩니다.

기본 개념:

1. 고정 크기의 윈도우: 시작점과 끝점을 가진 윈도우를 데이터의 왼쪽에서 오른쪽으로 움직이면서 연속된 부분 집합을 조사합니다.
2. 가변 크기의 윈도우: 일반적으로 두 개의 포인터(시작 포인터와 끝 포인터)를 사용하여 윈도우 크기를 동적으로 조절하면서 문제의 조건을 만족하는지 확인합니다.

자바스크립트로의 구현 예 (고정 크기의 윈도우를 사용하여 최대 부분 집합의 합 계산):

function maxSumOfSubarray(arr, k) {
    let maxSum = 0, windowSum = 0;

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

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

    return maxSum;
}

console.log(maxSumOfSubarray([2, 3, 4, 1, 5], 3));  // 출력: 10 (3 + 4 + 1 = 8, 4 + 1 + 5 = 10 중에서 10이 가장 큼)

슬라이딩 윈도우 기법은 최적화 문제나 특정 조건을 만족하는 연속적인 부분 집합을 찾을 때 특히 유용합니다. 배열이나 리스트에서 연속적인 부분 집합과 관련된 문제가 있으면 이 기법을 고려해 보는 것이 좋습니다.