[JS 알고리즘] 슬라이딩 윈도우 패턴 ( Sliding Window Pattern )

아래 강의를 듣고 내용을 정리한 포스트 입니다.

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

JavaScript (JS) Algorithms and Data Structures Masterclass

 

규모가 큰 데이터셋에서 하위 집합을 찾는경우에 유리한 슬라이딩 윈도우 패턴은 로직에 창문 요소가 를 하나 만듭니다.

창문은 단일 변수, 하위배열, 다른 문자열 등으로 이루어져 있습니다.

조건에 따라 창문을 이동시키며, 보통 인덱스의 시작위치에서 끝나는 위치에 도착하지만, 오른쪽끝이나 가운데에서도 시작할수도 있습니다.

 

언제 사용하는가 ?

- 입력으로 주어진 데이터의 특정한 하위집합을 찾을때
- 규모가 큰 데이터셋에서 하위 집합을 찾는 경우에 유리함

필요 조건 : 문자열, 배열
핵심 : 조건에 맞는 창문 요소를 만들고, 특정 위치에서 마지막 지점까지 이동시키며 윈도우의 맨앞과 맨끝의 요소만 가지고 연산을 수행

예제 1

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

위 함수는 배열과 숫자 하나를 전달하고, 2번째 인자의 숫자만큼 순서대로 값을 더했을때 가장 값이 큰 합계를 도출하는 함수입니다. 입력 배열은 정렬할 필요가 없이 정수만 있습니다.

function maxSubarraySum(arr: number[], num: number) {
  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);
  }
  return maxSum;
}

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

배열에 대해 루프를 돌때, 3개의 요소에 대해 모두 연산을 매번 할 필요가 없습니다. 이 경우에는 첫 루프에서 연산한 값에, 첫번째 인덱스의 값을 빼고 다음 인덱스의 값을 더해주기만 하면 됩니다.

이 개념 자체가 슬라이딩 윈도우 입니다. 윈도우 내의 모든 요소에 대해 루프를 돌지 않고, 맨앞의 요소와 맨끝의 요소만 가지고 전체 루프를 순회하는 로직입니다.

이와 같이, 슬라이딩 윈도우 개념을 적용하여 조건에 부합하는 값을 찾기위해 모든 요소에 대해 매번 루프를 도는것이 아닌, 전체 루프를 한번만 순회하도록 문제를 해결할수 있습니다.