슬라이딩 윈도우 알고리즘

슬라이딩 윈도우 알고리즘?

하나의 특정 범위를 지정해놓고, 윈도우를 이동시키면서 범위 내에 있는 원소들을 계산해주는 원리.

배열과 그 배열의 subArray(부분배열)의 원소들을 어떠한 조건하에 계산하는 상황에서 사용된다. O(n)의 시간복잡도.

ex. 구간 합 구하기, 일정한 사이즈의 범위 값 계산하기, 가장 긴 부분 문자열 구하기 등.

 

 

예제) 사이즈가 K인 부분배열의 최대 합을 구하시오.

Function maxSumOfArray(arr: number[], k:number){
  let windowSum = 0;
  let maxSum = -Infinity; // arr에 음수가 포함될 경우 대비

  for(let i = 0; i < arr.length; i++){
    windowSum += arr[i];
    if(i >= k-1){
        maxSum = Math.max(windowSum, maxSum);
        windowSum -= arr[i - (k-1)];	
    }
    return maxSum;
  }
}

maxSumOfArray([5,7,-1,14,3,12,1], 3) // 29

// K = 3
// [5,7,-1] -> 11
// [7,-1,14] -> 20
// [-1,14,3] -> 16
// [14,3,12] -> 29
// [3,12,1] -> 16
// [12,1,4] -> 17