[알고리즘] 기준점 간 이동 배열 패턴 (Sliding Window)

[알고리즘] 기준점 간 이동 배열 패턴 (Sliding Window)

슬라이딩 윈도우(Sliding Window) 알고리즘은 배열이나 리스트와 같은 데이터 구조에서 연속적인 서브 배열(subarray) 또는 서브 리스트(sublist) 문제를 해결하는 데 사용되는 최적화 기법입니다.

이 알고리즘을 사용하면 불필요한 계산을 줄이고 효율적으로 문제를 해결할 수 있습니다.

 

슬라이딩 윈도우 알고리즘은 고정된 크기의 "윈도우"(부분 배열)를 사용하여 배열을 반복적으로 순회하면서 윈도우의 시작점과 끝점을 이동시키는 방식입니다.

윈도우를 오른쪽으로 한 칸씩 슬라이드하면서, 새로운 요소를 추가하고 이전 요소를 제거하는 방식으로 문제를 해결합니다.

 

 

문제 [ 고정 크기 윈도우 ]

임의의 숫자 배열와 숫자 k가 주어졌을 때, 연속된 k개의 요소의 최대 합을 구하시오.

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

 

 

O(n^2)의 시간 복잡도 해결책

시간 복잡도 = O( n^2 )

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

 

 

 

O(n)의 시간 복잡도 해결책

시간 복잡도 = O( n )

function maxSubarraySum(arr, num) {
	let maxSum = 0;
    let temSum = 0;
    if (num > arr.length) {
    	return null;
    }
    for (let i = 0; i < num; i++) {
    	maxSum += arr[i];
    }
    for (let i = num; i < arr.length; i++) {
    	temSum = maxSum - arr[i - num] + arr[i];
        maxSum = Math.max(temSum, maxSum);
    }
    return maxSum;
}

 

접근 방식

1. 먼저, 배열의 처음 k개의 요소의 합을 계산하여 초기 윈도우의 합을 구합니다.
2. 그런 다음, 윈도우를 오른쪽으로 한 칸씩 슬라이드하면서 새로운 요소를 추가하고, 이전 요소를 제거하여 현재 윈도우의 합을 업데이트합니다.
3. 각 단계에서 최대 합을 갱신합니다.