Sliding Window Pattern

해당 글은 Udemy "JavaScript 알고리즘 & 자료구조 마스터 클래스" 수업을 기반으로 작성한 내용입니다.

 

슬라이딩 윈도우 패턴은 이름과 같이 고정된 창문이 일정한 범위를 유지하며 이동하는 알고리즘 패턴입니다. 해당 패턴은 배열이나 숫자의 일정한 범위를 이동하며 해당 데이터의 하위 집합을 찾는 경우에 유용합니다.

 

슬라이딩 윈도우 패턴을 이해해보자!

maxSubarraySum

해당 알고리즘은 arr(배열), n(숫자)을 인자로 받고 배열 arr의 n개의 연속된 요소들의 합의 최대값을 구하는 문제 입니다. 배열은 정수로 이루어져 있고 정렬될 필요는 없으며 빈 배열의 경우 null을 반환합니다.

function maxSubarraySum(arr, n) {
  if (n > arr.length) return null;

  let max = -Infinity;
  for (let i = 0; i < arr.length - n + 1; i++) {
    temp = 0;
    for (let j = 0; j < n; 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

 

가장 먼저 떠올릴 수 있는 방법은 위와 같습니다. 하지만 해당 로직은 O(n2)의 시간복잡도를 갖기 때문에 조금 더 나은 성능의 알고리즘이 필요해보입니다.

 

Sliding window pattern을 적용하여 알고리즘을 풀어보겠습니다.

function maxSubarraySum(arr, n) {
	let tempSum = 0;
  let maxSum = 0;

  if (arr.length < n) return null;

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

  for (let i = 0; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.math(maxSum, tempSum);
  }

  return maxSum;
}

• 먼저 최대값 maxSum과 그 값과 비교할 임시 최대값 tempSum 두 변수를 선언후 0을 할당한다.
• 얼리리턴으로 인자로 들어온 number n 이 배열의 길이보다 클 경우에는 null 을 반환한다.
• 반복문을 사용하여 maxSum 에 배열의 n-1 인덱스 까지의 합을 할당 한다.
• 반복문을 끝내고 나온 최대값 maxSum을 tempSum에 할당한다. (최초 실행시 maxSum 과 tempSum 의 값은 동일하다)
• 또 하나의 반복문을 순회하며 최대값을 사용하는데 사용했던 제일 앞 인덱스의 배열요소(arr[i - num])를 제거하고 그 다음 인덱스의 배열요소(arr[i])를 더하고 tempSum 에 합한 값을 할당한다.(이 부분이 sliding window pattern이 적용되는 부분이다)
• maxSum 에 Math.max를 이용하여 최대값을 할당해 준 뒤 해당 값을 반환한다.

 

해당 문제를 아래와 같은 방법으로 풀이할 수 도 있습니다.

function maxSubarraySum(arr, n) {
  let tempSum = 0;
  let maxSum = -Infinity;

  for (let i = 0; i < arr.length; i++) {
    tempSum += arr[i];
    if (i >= n - 1) {
      maxSum = Math.max(tempSum, maxSum);
      tempSum -= arr[i - (n - 1)];
    }
  }
  return maxSum;
}

 

Reference

https://www.youtube.com/watch?v=JWHjqjk9ZYc