[algorithm] Sliding Window 패턴 (슬라이딩 윈도우 패턴)

Sliding Window Pattern (슬라이딩 윈도우 패턴)

슬라이딩 윈도우 패턴은 배열이나 문자열 같은 데이터 집합에서 연속적인 부분 집합을 효율적으로 추적할 때 사용하는 패턴이다.
이 패턴을 사용해서, 특정 조건에 따라 윈도우(범위)를 조정하여 사용한다.

 

<주요 개념>

1. 윈도우 : 연속된 데이터의 부분 집합, 특정 구간을 나타낸다.

2. 윈도우 이동 : 특정 조건에 따라서, 윈도우 위치를 이동 시킨다. 주로 윈도우를 왼쪽에서 오른쪽으로 이동시킨다.

3. 효율성 : 매번 전체 배열을 탐색할 필요 없이 윈도우의 시작과 끝만을 조작하여 이전 값을 재사용하는 방식으로 문제를 처리할 수 있다.

 

<예시>

1. 문제
Write a function called maxSubarraySum which accepts an array of integers and a number called n.
The function should calculate the maximum sum of n consecutive elements in the array.

 

2. 비효율적인 코드 예시
아래 코드의 시간 복잡도는 O(N^2)이다. num이 길어짐에 따라서,  임시 합계를 구하는 반복문과, 전체 배열을 순회하는 반복문이 동시에 늘어나게 된다.

function maxSubarraySum(arr, num) {
    if (arr.length < num) {
        return null;
    }
    maxSum = -Infinity;
    for (let i = 0; i < arr.length - num + 1; i++) {
        tempSum = 0;
        for (let j = 0; j < num; j++) {
            tempSum += arr[i + j];
        }
        if (tempSum > maxSum) {
            maxSum = tempSum
        }
    }
    return maxSum;
}

 

3. 효율적인 코드 예시
아래 코드의 시간 복잡도는 O(N)이다. num이 길어지더라도 전체 배열을 한번만 순회하여 최대값을 찾을 수 있다.

function maxSubarraySumRefactor(arr, num) {
    let maxSum = 0;
    let tempSum = 0;
    if (arr.length < num) return null;
    for (let i = 0; i < num; i++) {
        maxSum += arr[i];
    }
    tempSum = maxSum;
    // tempSum을 가지고, 맨 앞과 맨 뒤를 추가한다.
    // 시작 시점은 num에서 시작할 수 있다.
    // 처음에 더해야할 숫자는 arr[num]이고, 빼야할 숫자는 arr[0]이다.
    // 두번째로 더해야할 숫자는 arr[num + 1]이고, 빼야할 숫자는 arr[1]이다.
    for (let i = 0; num + i < arr.length; i++) {
        tempSum = tempSum - arr[i] + arr[i+n];
        maxSum = Math.max(maxSum, tempSum)
    }
    return maxSum;
}

4. 테스트용 결과값

maxSubarraySum([1,2,5,2,8,1,5], 2) // 10
maxSubarraySum([1,2,5,2,8,1,5], 4) // 17
maxSubarraySum([4, 2, 1, 6], 1) // 6
maxSubarraySum([4, 2, 1, 6, 2], 4) // 13
maxSubarraySum([], 4) // null