슬라이딩윈도우 알고리즘(feat.Javascript)

슬라이딩윈도우 알고리즘을 적용한 문제를 풀면서 고민한점과 풀이 방법에 대해서 적고자 합니다.

1 . 정의

슬라이딩 윈도우(Sliding Window) 알고리즘은 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용한 알고리즘이다. 해당값을 창문처럼 묶는다고 하여 붙여진 이름이고 이는 매번 처리되는 중복된 요소를 버리지 않고 재사용함으로써 낭비되는 계산을 하지 않음으로써 효율적으로 처리하는 방법입니다.

2 . 실제 적용

문제
현수의 아빠는 제과점을 운영합니다.
현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 15 11 20 25 10 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.
여러분이 현수를 도와주세요.

입력
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

출력
첫 줄에 최대 매출액을 출력합니다.

이를 풀기 위해서 가장 간단한 방법인 이중 For문을 사용하는 방법이 있습니다.
해당배열을 i번쨰의 값부터 주어진k값개 만큼 더해서 해당값이 기존값보다 크다면 그 값으로 바꿔주면서 answer를 출력합니다.

function mySolution(k, arr) {
        let answer = 0;
        for (i = 0; i < arr.length - k + 1; i++) {
          let sum = 0;
          for (j = i; j < i + k; j++) {
            sum += arr[j];
          }
          if (sum > answer) answer = sum;
        }
        return answer;
      }

      let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
      console.log(solution(3, a));

하지만 이렇게 작성하면 해당 값은 시간복잡도 n * k를 가지게 됩니다.
하지만 이를 슬라이딩 윈도우 개념을 적용하면 n번의 시간복잡도를 가지게 되므로 효율적인 알고리즘이며 이제 실제로 적용한 코드를 확인하겠습니다.

function solution(k, arr) {
        let answer,
          sum = 0;
        for (let i = 0; i < k; i++) sum += arr[i];
        answer = sum;
        for (let i = k; i < arr.length; i++) {
          sum += arr[i] - arr[i - k];
          answer = Math.max(answer, sum);
        }
        return answer;
      }

해당값을 풀어서 설명하자면 처음부터 3개의 값을 비교해서 k번쨰의 값과 k-i번쨰의 값의 차를 sum에 더해서 이 값과 answer값을 비교해서 더큰값을 answer에 저장합니다.
배열 a의 첫 세개의 값이 12,15,11이므로 이 세개의 값의 합인 sum은 38입니다. 이제 우리의 슬라이딩윈도우 알고리즘을 사용하면 a[3]의 값과 a[0]의 차를 sum에 더해주면 46이므로 우리의 answer보다 크기때문에 해당값으로 sum을 바꿔줍니다.
이를 한번더 적용해보면 a[4]의 값과 a[1]의 차는 10이므로 우리의 sum은 56이되면서 이를 answer로 대치해줍니다.
마지막으로 한번더 적용해보면 a[5]의 값과 a[2]의 차는 -1이므로 우리의 sum은 55가되면서 기존에 있던 answer가 유지됩니다.

이런식으로 배열의 마지막 index까지 간다면 해당 함수는 끝나고 마지막으로 대치된 answer의 값이 우리의 정답이 되면서 해당 문제의 정답은 56이됩니다.

3 . 끝으로

실제 이중 for문보다 시간복잡도를 간단하게 계산할수 있는 알고리즘이고 특정한 상황에서 쓰면 효율적일것 같습니다.
혹시나 궁금한점이 있거나 내용에 문제가 있다면 댓글 남겨주시면 감사하겠습니다:)