슬라이딩 윈도우 패턴

JavaScript 알고리즘 & 자료구조 마스터 클래스 강의를 듣고 작성하는 강의노트

• '슬라이딩 윈도우(Sliding Window)'이라는 명칭은 공식 명칭이 아니다. 본 글에서는 이를 '슬라이딩 윈도우'라고 명명한다.

슬라이딩 윈도우 패턴의 개념

배열이나 리스트 요소의 일정 범위의 값을 비교할 때 사용하면 유용한 알고리즘이다.
예를 들어 한 단어의 문자들 중 연속된 고유 문자의 길이가 가장 긴 부분을 출력할 때 슬라이딩 윈도우와 같은 패턴을 사용할 수 있다.

ex. 'hellothere' 에서는 'lother' 가 가장 길다.)

Example

• maxSubarraySum 함수가 있다.
• 첫번째 인자로 하나의 배열을 전달 받는다.
• 두번째 인자로 한 숫자로 전달 받는다.
• 인자로 받은 배열 내, 두번째 인자만큼 연속된 숫자들의 합이 가장 큰 숫자들의 합을 반환하는 함수다.
• 배열의 수가 두번째 인자보다 작을 때 null을 반환한다.

function maxSubarraySum(arr, num) {
  if (num > arr.length) {
    return null;
  }
  let 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([1, 2, 5, 2, 8, 1, 5], 2); // 10
maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4); // 17
maxSubarraySum([4, 2, 1, 6], 1); // 6
maxSubarraySum([4, 2, 1, 6, 2], 4); // 13
maxSubarraySum([], 4); // null

• max를 -Infinity로 표현한 것은 배열이 음수로 구성되어 있을 경우 가장 큰 합 또한 음수일 것이기 때문이다.

Nested loop(중첩 루프)로 인해 시간 복잡도는 O(N2)

위와 같이 간단한 예제에서는 문제가 되지 않지만 방대한 길이의 배열, 방대한 양의 수만큼의 합을 구하게 된다면 굉장히 비효율적인 방식이 될 것이다. 이를 슬라이딩 윈도우 패턴을 통해 리팩토링 해보자.

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];
  }
  temSum = 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, 4, 1, 3, 6, 5, 6], 5);

먼저 2, 6, 9, 2, 1 부분을 검사하고
다음 6, 9, 2, 1, 8 부분을 검사하고
그 다음 9, 2, 1, 8, 5 부분을 검사하고 ...

위 과정을 반복하는데 처음 더한 합에서 첫번재 수를 빼고 다음 루프의 첫번째 수를 더하기만 하면 된다.

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

시간 복잡도: O(N)