[Algorithm] Sliding Window

The Sliding Window algorithm is one way programmers can move towards simplicity in their code. This algorithm is exactly as it sounds; a window is formed over some part of data, and this window can slide over the data to capture different portions of it.

이름이 의미하는 그대로, 특정 조건을 충족할 때까지 window를 sliding하며 값을 찾는 알고리즘이다.

[a b c d e f g h] // original array

[a b c]
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h]

문제 1

array와 숫자 n을 받아서, array를 돌면서 n만큼 연속된 숫자의 가장 큰 합을 반환하는 함수를 만드세요.

예를 들어,
maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3)이면, 배열안에서 3만큼 연속된 수의 합이 가장 큰 수는 8, 5, 6이므로, 합은 17이다. 따라서 17을 반환한다.

// Bad!
function maxSubarraySum(arr, n) {
  if (arr.length < n) return null;

  let max = -Infinity;

  for (let i = 0; i < arr.length - n + 1; i++) {
    let temp = 0;
    for (let j = 0; j < n; j++) {
      temp += arr[i + j];
    }
    if (temp > max) {
      max = temp;
    }
  }
  console.log(max);
  return max;
}

// Good!
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);
  }
  console.log(maxSum);
  return maxSum;
}

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

첫번째 코드는 nested loop을 사용했기 때문에 효율성이 떨어진다.

두번째 코드는 sliding window pattern을 사용했다. 가장 처음 3개의 숫자의 합을 구했고, 그 이후에는 tempSum - arr[i - num]로 이전의 숫자를 제거 한다. 그리고 arr[i]로 다음 숫자를 추가한다.