[Algorithm] 슬라이딩 윈도우 알고리즘(Sliding Window Algorithm)

1. 슬라이딩 윈도우 알고리즘(Sliding Window Algorithm)이란?

출처 https://learning-e.tistory.com/36

 

슬라이딩 윈도우 알고리즘은 고정 사이즈의 윈도우를 이동시키면서,

윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다.

 

이때 윈도우 안에 있는 데이터는, 양 끝에 있는 원소들만 변화한다. 

 

 

2. 예시

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

 

//내코드
function solution(k, arr) {
    let answer = sum = 0;

    for (let i = 0; i < arr.length - k; i++) {
        let num = k;

        while (k > 0) {
            sum += arr[k + i];
            k--;
        }

        if (answer < sum) answer = sum

        k = num;
        sum = 0;
    }

    return answer;
}

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

 

우선 슬라이딩 윈도우 알고리즘을 사용하지 않은 풀이방법이다.

for문과 while문을 이용하였다.

 

for문을 통해 날짜별로 반복문을 돌리고, 해당 날짜를 기준으로 각 K일까지의 값을 합한뒤 가장 큰 값을 answer에 넣어줬다.

위 풀이방법의 시간복잡도는 O(n^2)이다.

 

그러나 슬라이딩 윈도우 알고리즘을 사용하면 O(n)으로 끝낼 수 있다. 

아래는 슬라이딩 윈도우 알고리즘 풀이 방법이다.

 

//강의코드 
function solution(k, arr) {
    let answer = sum = 0;

    //첫 창문 구하기(처음 값 구하기)
    //처음 창문을 만들고 그 창문을 한 칸씩 밀고 나가면 됨 
    for (let i = 0; i < k; i++) sum += arr[i];

    for (let i = k; i <= arr.length - 1; i++) {
        sum += (arr[i] - arr[i - k]);
        if (answer < sum) answer = sum;
        //answer=Math.max(answer, sum )
    }

    return answer;
}

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

 

슬라이딩 윈도우 알고리즘 풀이 방식이다.

위에서부터 살펴보자. 

 

for (let i = 0; i < k; i++) sum += arr[i];

 

우선 슬라이딩 윈도우는 고정된 사이즈의 윈도우를 생성한 후, 앞으로 계속 나아가면서 문제를 풀이하는 방식이다.

따라서 맨 처음 고정된 사이즈의 윈도우를 생성해줘야 한다.

 

위 문제에선 '연속된 K일'이라는 사이즈가 주어졌기 때문에, K만큼의 윈도우를 만들어준다.

 

 

이런식으로 생성된다고 생각하면 된다.

 

 

for (let i = k; i <= arr.length - 1; i++) {
    sum += (arr[i] - arr[i - k]);
    if (answer < sum) answer = sum;
    //answer=Math.max(answer, sum )
}

 

그 후 윈도우를 한칸씩 앞으로 전진하며 합을 구한다.

 

슬라이딩 윈도우 알고리즘은 앞에서 말했다싶이 양 끝의 값만 바뀌면 된다.

이미 k번째까지의 숫자의 합이 들어있기 때문에 그 다음 숫자를 더하고, 첫 번째 숫자를 빼주면 된다.

 

즉, K다음 숫자인 i를 더해주고 첫 번째 숫자인 k-i 번째 값을 뺀 값이 다음 합이 되는 것이다. 

그리고 해당 합 중에 더 큰 수를 answer에 저장해주면 된다. 

 

 

그러면 윈도우는 이런식으로 이동할 것이다.