[Algorithm] 알고리즘 기본 패턴 3 - Sliding Window

3. Sliding Window

https://www.geeksforgeeks.org/window-sliding-technique/

 

배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인
해당 데이터의 하위 집합을 찾는 경우에 유용합니다.

창문을 하나 만들어야 합니다. 

여기서 말하는 창문이란 개념은 주어진 데이터의 범위를 나타냅니다.

그 창문을 만들고 데이터 안에서 창문을 여는 것처럼 이동을 시키며

주어진 조건을 클리어하는 알고리즘 패턴입니다.

 

이 기법은 윈도우의 크기를 나타내는 변수와 하위 배열, 또는 다른 문자열이 주어지며,

윈도우의 크기는 고정되거나 가변적인 크기가 될 수 있습니다.

조건에 따라 창문을 이동시키며, 시작 위치에서 시작하면
보통 왼쪽에서 오른쪽으로 이동합니다. 오른쪽에서 왼쪽으로 이동도 가능하고
가운데 위치에서 시작할 수도 있습니다.

그러나 보통 창문을 왼쪽, 즉, 요소의 시작 위치, 또는 배열이나 문자열의 시작 위치에서
끝나는 위치로 이동합니다.

규모가 큰 데이터셋에서 데이터의 하위 집합을 추적하는 이런 문제에 있어서는 유용합니다.

 

 

 

 

이런 식으로 창문을 이동하면서 현재 윈도우의 값을 구합니다.

 

sum = 이전 윈도우 범위 내의 값의 합 - 이전 원도위의 가장 왼쪽값 +  윈도우 새 위치의 가장 오른쪽 값

maxSum = Math.max(maxSum, sum)

 

이렇게 비교해서 큰 값을 취하면 됩니다.

 

 

1. 고정 크기 Sliding Window

1. 필요한 창의 크기를 windowSize 변수로 지정했습니다 .
2. 첫 번째 창에 대한 결과를 계산합니다. 즉, 데이터 구조의 처음 windowSize 개 요소를 포함합니다.
3. 그런 다음 루프를 사용하여 창을 1씩 밀고 창마다 결과 창을 계속 계산합니다.

 

제가 이전 풀던 코드는 다음과 같습니다

function maxSubarraySum(arr, windowSize) {
    if(windowSize > arr.length) return null
    
    // 초기 result 값을 -Infinity로 설정 (음수 값도 처리하기 위해)
    let result = -Infinity
    
    for(let i = 0; i < arr.length - windowSize + 1; i++){
        let sum = arr.slice(0 + i, i + windowSize).reduce((a,b) => a + b)
        if(sum > result) result = sum
    }
    return result
}

배열의 길이 k, windowSize를 n 이라고 할 때,

위 코드의 시간 복잡도는

 

1. 외부 루프: O(n-k+1) ≈ O(n) 

- 배열을 windowSize만큼 순회

 

2. 각 루프 내부 연산:

 - slice(): O(k) - windowSize 만큼의 요소를 복사

 - reduce(): O(k) - 복사된 배열의 모든 요소를 순회하며 더함

 

3. 전체 연산:

 - 각 루프에서 O(k)의 작업을 O(n)번 수행 

 - 따라서 O(n) * O(k) = O(n*k)

 

 

 

다음은 슬라이딩 윈도우 예시입니다.

function slidingWindow(arr, windowSize) {
    if(windowSize > arr.length) return null
    
    let sum = 0;
    // 첫 윈도우 계산: O(k)
    for(let i = 0; i < windowSize; i++) {
        sum += arr[i];
    }
    
    let maxSum = sum;
    // 슬라이딩 윈도우: O(n-k)
    for(let i = windowSize; i < arr.length; i++) {
        sum = sum - arr[i - windowSize] + arr[i];
        maxSum = Math.max(maxSum, sum);
    }
    
    return maxSum;
}

 

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 의 배열이 주어지고 차례대로 4개의 값을 가진다면

 

1,2,3,4 의 첫번째 합을 maxSum 에 저장 후,

이전 윈도우  첫번째 값 [0]과

다음 윈도우의 마지막 값 [4] 의 값을 비교 후, 더 큰값을 maxSum 에 대입해나가는 방식입니다 

 

시간 복잡도는 O(n)입니다.

 

 

2. 가변 크기 Sliding Window

 

1. 조건이 참이 될 때까지 오른쪽 포인터를 하나씩 증가시킵니다.
2. 어느 단계에서든 조건이 일치하지 않으면 왼쪽 포인터를 늘려서 창의 크기를 줄입니다.
3. 조건이 만족되면 오른쪽 포인터를 증가시키고 1단계를 따릅니다.
4. 배열의 끝에 도달할 때까지 위 단계를 반복합니다.

문제 )

양수 배열과 양수, 두 개의 매개 변수를 받아들이는 minSubArrayLen이라는 함수를 작성하세요.

이 함수는 합이 함수에 전달된 정수보다 크거나 같은 인접한 하위 배열의 최소 길이를 반환해야 합니다. 값이 없는 경우 0을 반환합니다.

 

예시 ) 

minSubArrayLen([2,3,1,2,4,3], 7) // 2 -> because [4,3] is the smallest subarray
minSubArrayLen([2,1,6,5,4], 9) // 2 -> because [5,4] is the smallest subarray
minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // 1 -> because [62] is greater than 52
minSubArrayLen([1,4,16,22,5,7,8,9,10],39) // 3
minSubArrayLen([1,4,16,22,5,7,8,9,10],55) // 5
minSubArrayLen([4, 3, 3, 8, 1, 2, 3], 11) // 2
minSubArrayLen([1,4,16,22,5,7,8,9,10],95) // 0

 

조건 ) 

Time Complexity - O(n)
Space Complexity - O(1)

 

function minSubArrayLen(arr, target) {
    let total = 0;
    let start = 0;
    let minLen = Infinity;
    
    for (let end = 0; end < arr.length; end++) {
        total += arr[end];
        
        // 현재 합이 target보다 크거나 같으면
        // 윈도우를 줄여가며 최소 길이 찾기
        while (total >= target) {
            minLen = Math.min(minLen, end - start + 1);
            total -= arr[start];
            start++;
        }
    }
    
    return minLen === Infinity ? 0 : minLen;
}

 

 

참고

https://www.geeksforgeeks.org/window-sliding-technique/

Sliding Window Technique - GeeksforGeeks

 

 

 

다음 알아볼 패턴들..

Divide and Conquer
Dynamic Programming
Greedy Algorithms
Backtracking

 

 

지난 관련글

 

1. Frequency Counter (빈도수 세기)

https://daunje0.tistory.com/190

[Algorithm] 알고리즘 기본 패턴 1 - Frequency Counter (빈도수 세기)

 

2. Multiple Pointers (다중 포인터)

https://daunje0.tistory.com/191

[Algorithm] 알고리즘 기본 패턴 2 - Multiple Pointers (다중 포인터)