슬라이딩 윈도우

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

 

배열이나 문자열에서 일련의 데이터를 찾는 경우다.

예를 들면 특정 문자열에서 고유한 문자가 연속되어야 하는 경우,

"hellothere"

--> hel --> el --> l --> lother 

 

또는 배열에서, 일련의 두 원소의 합이 가장 큰 경우를 구하려 할 때

maxSubarraySum([1,2,5,2,8,1,5], 2) ==> 10

 

이런 경우에 윈도우를 하나 만들어야 한다. 이 윈도우는 단일 변수, 하위 배열, 또는 문자열이 될 수도 있다.

조건에 따라 이 창문을 이동시킨다. 이동 시작위치와 방향은 자유지만, 일반적으로는 왼쪽(시작점)에서 오른쪽(종료지점)으로 이동한다.

경우에 따라 새로운 윈도우를 만들기도 한다.

 

maxSubarraySum을 슬라이딩 윈도우 방식을 사용하지 않고 작성한다면 아래와 같다.

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)

 

 

슬라이딩 윈도우를 사용하는 경우 시간 복잡도가 O(n^2)에서 O(n)으로 줄어든다.

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) //19