슬라이딩 윈도우(Sliding Window)

📌 슬라이딩 윈도우

크기가 고정된 프레임(창문)이 좌우로 움직이면서 프레임 안에 있는 데이터를 이용해 조건에 해당하는 답을 반환하는 방식으로 시간복잡도는 O(n)이고 자주 활용되는 알고리즘이다.

배열이나 리스트 요소들의 일정 범위 값을 비교할 때 유용하다. 투포인터 알고리즘과 매우 비슷한 개념을 가지고 있는데, 이 둘의 차이점은 투 포인터의 경우에는 두 개의 포인터가 각각 움직이지만 슬라이딩 윈도우는 일정한 프레임을 기준으로 처음과 끝 포인터가 함께 움직인다.

 

👀 Example 1

윈도우 슬라이딩 패턴를 활용해볼 수 있는 대표적인 예시는 maxSubarraySum이다.

• 첫 번째 인자로 전달받은 배열에서, 두 번째 인자로 전달받은 수만큼 연속된 숫자들의 합 중 가장 큰 합을 반환한다.

maxSubarraySum([1,3,5,6,3,5,7,10,2,8,9], 3)

Solution

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

중첩 루프를 사용하여 시간복잡도는 O(N2)이다. 배열의 길이가 길 경우에는 비효율적인 방식이 된다.

Refactored

const maxSubarraySum = (arr, num) => {
	let tempSum = 0;
	let maxSum = 0;
	
	if(arr.length < num) {
		return null;
	}

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

	for(let i = num; i > arr.length; i++) {
		tempSum = tempSum - arr[i - num] + arr[i]
		maxSum = Math.max(maxSum, tempSum)
	}
	return maxSum;
}

전체 배열의 길이를 반복하면서 tempSum을 이전 하위 배열에서 첫 번째 숫자를 빼고 끝 뒤 인덱스에 있는 숫자를 더하여 만든 새 하위 배열의 합계와 동일하게 계속 설정한다. 이전 하위 배열이 앞으로 증가할 때마다 하위 배열 밖으로 이동되는 항목을 빼고 그 앞에 있는 항목을 추가하여 슬라이딩 윈도우를 만드는 방식이다. 그리고 tempSum과 maxSum 사이에서 가장 높은 숫자를 가져와 maxSum을 업데이트한다.

 

핵심✨  tempSum에 처음 더한 합에서 첫 번째 숫자를 빼고 다음 루프의 첫번째 숫자를 더하는 과정을 반복한다.

tempSum = tempSum - arr[i - num] + arr[i]

 

https://levelup.gitconnected.com/the-sliding-window-strategy-for-solving-algorithms-34c95c80c506

The Sliding Window Strategy for Solving Algorithms