[알고리즘&자료구조] 슬라이딩 윈도우 알고리즘, Sliding Window

슬라이딩 윈도우란?

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘

여기서 말하는 윈도우와 슬라이딩은 창문 틀에서 창문이 슬라이딩 하는 것 같은 알고리즘이라는 뜻

프로그램을 작성할때나 코딩테스트에서 리스트를 활용하는 경우는 굉장히 많다.
일반적으로 인덱스를 처음부터 끝까지 완전 탐색을 하게 되는데, 완전 탐색을 할 경우 효율성이 좋지 않을 때 활용할 수 있는 알고리즘 3가지는 다음과 같다.

1. Two Pointer
2. Sliding Window
3. Prefix Sum

문제설명

주어진 Array에서 주어진 number 만큼의 연속되게 붙어있는 값들을 더했을때 가장 큰 값 max를 구해야한다.

예를들어 maxSubarraySum([2,6,9,2,1,8,5,6,3],3) 라는 형식으로 주어진다면 배열 [2,6,9,2,1,8,5,6,3] 에서 3만큼 연속된 값들을 더해서 가장 큰값을 구하는 것이다. 

 

기본 2중 for문 이용한 완전탐색(Brute Force)

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;
}

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

2중for문으로 어디까지 더할지에 대한 for문과 주어진 숫자만큼더할 for문을 만들어서 차례차례 더해가면서 max값을 업데이트하게 되는데 이렇게 되면 빅오 O(n^2)가 되므로 비효율적이다

 

슬라이딩 윈도우를 이용한 리펙토링 코드

function maxSubarraySum(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;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

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

슬라이딩윈도우 접근법 인데, 한칸한칸 이동하면서 더하는게 아니라 한번 더한 값(max)에서 맨첫번째 array값을 뺴고 새로운 array값만 더해주는걸로 비교해주는 것이다. 이렇게하면 2중 for문없이도 O(N)으로 가능하게된다.