문제 해결 패턴 - Sliding Window

Sliding Window(슬라이딩 윈도우)

배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다.

 

 

O(n^2) 인 코드

전자는 중첩된 루프문으로 배열에 숫자가 백만개 있을 경우 1,000,000 * 1,000,000 번 반복해야 하는 문제가 있다.

 

 

O(n) 으로 해결되는 코드

후자의 경우 루프를 배열에 한 번만 적용하여 O(n)으로 해결할 수 있다. 이것이 슬라이딩 윈도우

 

function maxSubarraySum(arr, num) {
  if (arr.length < num) return null;

  let tempMaxNum = 0;
  let maxNum = 0;
  for (let idx = 0; idx < num; idx++) {
    tempMaxNum += arr[idx];
  }
  // tempMaxNum = 2+6+9 = 17

  for (let idx = num; idx < arr.length; idx++) {
    tempMaxNum = tempMaxNum + arr[idx] - arr[idx - num]; // tempMaxNum = 17+2-2
    maxNum = Math.max(tempMaxNum, maxNum);
  }
  return maxNum;
}

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

// 배열(arr)과 숫자(num)를 입력받고,
// arr에서 연속된 num 중에서 가장 큰 값을 리턴
// ex ) 2,6,9 -> 17 , 6,9,2 -> 17, ... 8,5,6 -> 19 => return 19

 

 

본 내용은 작성자가 (Udemy) JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 듣고 정리 및 메모한 내용입니다.  오역 및 오개념이 있을 수 있으니 바로잡기 위해 문제가 있는 경우 댓글 남겨주시면 매우 감사하겠습니다.

https://www.udemy.com/course/best-javascript-data-structures/

JavaScript (JS) Algorithms and Data Structures Masterclass