얌생

슬라이딩 윈도우 알고리즘

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘.

배열이나 리스트의 요소 중 일정 범위의 값을 비교할때 사용하면 유용하다.

• 선형 공간 ( 1차원 배열 )을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다.

예제 )

const n = 10; // N일 - 배열의 길이
const k = 3; // W 창문의 넓이
const arr = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15]; // 1차원 고정배열

function solution(n, k, arr) {
  let result = 0; // 길이 k의 부분 수열의 요소 전체 합의 최댓값
  let sum = 0; // 특정 부분 수열의 전체 합

  // 배열의 가장 왼쪽부터 k까지의 값의 합을 sum에 담음
  for (let i = 0; i < k; i++) {
    sum += arr[i];
  }

  result = sum;

  // k는 고정적이므로 새롭게 갱신되는 arr[i]와 기존 arr[i - k]를 빼줌
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    // 최대 합을 비교해서 갱신
    result = Math.max(result, sum);
  }

  return result;
}

console.log(solution(n, k, arr));

참고 :https://velog.io/@ninto_2/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98