home

    23-11-12

    (알고리즘) 슬라이딩 윈도우 with JavaScript

    슬라이딩 윈도우를 자바스크립트로 구현해보자.

    슬라이딩 윈도우란?

    slidingwindow

    슬라이딩 윈도우 기법은 배열 또는 문자열에서 고정 크기의 창(윈도우)를 유지하면서 특정 조건을 충족하는 부분 배열이나 부분 문자열을 찾는 기법이다.

    위의 이미지에 [1, 15, 1, 2, 6, 12, 5, 7] 이라는 배열이 있다. 연속적인 4개의 숫자의 합이 가장 큰 값을 구하자고 하자

    1. 초기에 첫 4개의 숫자로 윈도우를 설정하고 합을 구합니다.
      • 윈도우: [1, 15, 1, 2], 합: 19
    2. 다음으로 윈도우를 한 칸씩 오른쪽으로 이동하면서 새로운 합을 계산합니다.
      • 윈도우: [15, 1, 2, 6], 합: 24
      • 윈도우: [1, 2, 6, 12], 합: 21
      • 윈도우: [2, 6, 12, 5], 합: 25
      • 윈도우: [6, 12, 5, 7], 합: 30

    슬라이딩 윈도를 사용하면 윈도우를 이동하면서 연속적인 부분 배열의 합을 효율적으로 구할 수 있다.

     
    function maxSubarraySum(arr, num) {
      let maxSum = 0;
      let tempSum = 0;
      
        // // 우선 첫 번째 합을 maxSum에 저장
      for (let i = 0; i < num; i++) { 
        maxSum += arr[i];
      }
      tempSum = maxSum;
     
      // arr[0] 빼고 arr[num] 더하면 새로운 window.// 이것을 반복
      for (let i = num; i < arr.length; i++) {
        tempSum = tempSum - arr[i - num] + arr[i];
        maxSum = Math.max(maxSum, tempSum);
      }
      return maxSum;
    }
          
    maxSubarraySum([1, 15, 1, 2, 6, 12, 5, 7], 4); // 30

    이미지 출처
    https://dev.to/mwong068/sliding-window-technique-in-ruby-3og4