[Algorithm] Sliding Window

suyeonme·2021년 3월 1일
1

Algorithm

목록 보기
4/4
post-thumbnail

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.

문제 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]로 다음 숫자를 추가한다.

profile
Frontend Engineer.

1개의 댓글

comment-user-thumbnail
2021년 4월 9일

올려주신 글들은 잘 보고 있습니다!
합이 17이라고 해 주신 부분 19가 맞는거 같아 살포시 댓글 놓고 갑니다~

답글 달기