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

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

• 일정한 범위(Window)를 가지면서 이동(Sliding)하는 알고리즘이다.

• 배열또는 리스트 요소의 일정 범위 값을 비교할 때 유용하다.

 

ex) 양의 정수로 구성된 배열 [2, 4, 7, 10, 8, 4]에서 연속된 요소 3개의 합이 가장 큰 값은?

단순한 이중 for문을 사용한 방법은 아래와 같다.

#include <iostream>
#define SIZE 6

using namespace std;

int main(void) {

    int array[SIZE] = {2, 4, 7, 10, 8, 4};

    const int windowSize = 3;
    int max_sum = 0;

    for (int i = 0; i < SIZE - windowSize + 1; i++) {
        int window_sum = 0;
        for (int j = i; j < i + windowSize; j++) {
            window_sum += array[j];
        }
        max_sum = (max_sum > window_sum) ? max_sum : window_sum;
    }

    cout << "Result : " << max_sum;

    return 0;
}

// Result : 25
// (7 + 10 + 8)

데이터가 적을때는 문제가 없다. 하지만 데이터가 많아진다면 비효율적인 코드가 되는데 슬라이딩 알고리즘이 바로 해결책이 된다.

슬라이딩 운도우 알고리즘은 일정한 범위를 가지고 있는 것을 유지하면서 이동하는 것이다.

위 이미지처럼 범위가 5인 서브 배열을 탐색하는 경우 0~ 4일 때 와 1  ~ 5일 때의 서브 배열은 1 ~ 4 범위가 중복된다.

이러한 공통 요소들을 재사용 하는 방법이 슬라이딩 윈도우 알고리즘의 핵심이다.

#include <iostream>
#define SIZE 6

using namespace std;

int main(void) {

    int array[SIZE] = {2, 4, 7, 10, 8, 4};

    const int windowSize = 3;
    int max_sum = 0, window_sum = 0, window_start = 0;

    for (int window_end = 0; window_end < SIZE; window_end++) {
    	
        // 슬라이딩 윈도우 범위가 윈도우 사이즈보다 커진경우
        if (window_end > windowSize - 1) {
            max_sum = (max_sum > window_sum) ? max_sum : window_sum;
            window_sum -= array[window_start++]; // 범위를 벗어난 요소를 합에서 제거후 윈도우 시작 인덱스 증가
        }

        window_sum += array[window_end];
    }

    cout << "Result : " << max_sum;

    return 0;
}

첫번째 루프

• k : windowSize(윈도우의 사이즈)
• window_start : 윈도우 시작 index
• window_start : 윈도우 끝 index
• window_sum : 윈도우(서브 배열) 합

윈도우의 범위가 윈도우 사이즈보다 커질 때까지는 요소들을 더하고, 이후부터는 사이즈 밖의 요소들을 빼준다.

서브 배열의 합을 매번 구할 필요가 없이 모든 요소를 한 번에 순회하여 최댓값을 구할 수 있다.

 

 

<참고자료>

blog.fakecoding.com/archives/algorithm-slidingwindow/

[알고리즘] 슬라이딩 윈도우 알고리즘

ramees.tistory.com/52

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