슬라이딩 윈도우 알고리즘

슬라이딩 윈도우의 작동 방법

슬라이딩 윈도우 알고리즘은 배열이나 리스트의 요소의 일정 범위의 값을 비교할 떄 사용하면 유용한 알고리즘이다.

 

예를 들어 배열의 크기가 

5이고 길이가 2인 서브배열 중 서브배열의 합이 가장 큰 서브배열을 구한다고 생각해보자

 

첫번째 방법은 이중 포문을 돌리면서 특정 길이만큼 순회하며 합을 구하는 방법이다.

 

예를 들어 배열의 크기가 5이고 {1,2,3,4,5}, 길이가 2인 서브배열의 합의 최대값을 구해보자

 

#include <iostream>

using namespace std;

int main(void){

int array[5] = {1,2,3,4,5};

int array_size = 5; //배열의 크기가 5이고 길이가 2인 서브배열의 합의 최대값 ->

int length = 2;

int max_sum = -1;

 

for(int i = 0;i<array_size-length + 1;i++){

int sum = 0;

for(int j = i;j<i+length;j++){

sum = sum + array[j];

}

if(max_sum < sum){

max_sum = sum;

}

}

cout << max_sum;

}

 

이렇게 2중 루프를 돌리면 5+4로 9가 나오고 데이터가 많지 않다면 괜찮다.  

 

그러나 데이터가 많아지면 많아질수록 효과적이고 효율적인 코드를 작성해야 한다.

 

2중 루프를 돌떄 알 수 있는 사실은 중복되는 요소가 존재한다는 것이다.

 

{1,2,3,4,5}이고 길이가 2라고 했을때

 

처음 서브배열의 합 = 1+2

두번쨰 서브배열의 합 = 2+3 ->이때 2가 중복되는 요소이다.

세번째 서브배열의 합 = 3+4 ->이떄 3이 중복되는 요소이다.

 

이렇게 중복되는 요소를 다시 사용한다면 더 효과적인 코드를 작성 할 수 있다.

---

 

개선된 코드 ->

 

#include <iostream>

using namespace std;

 

int main(void){

 

   int array[5] = {1,2,3,4,5};

   int array_size = 5; //배열의 크기가 5이고 길이가 2인 서브배열의 합의 최대값 ->

   int length = 2;

 

    int max_sum = -1;

    int sum = 0;

 

    for(int i = 0;i<length;i++){

        sum = sum + array[i];

    }

 

    max_sum = sum;

 

    for(int i = length;i<array_size;i++){

        sum = sum + array[i];

        sum = sum - array[i-length];

        if(sum > max_sum){

            max_sum = sum;

        }

 

    }

    cout << max_sum;

}

---

처음 sum값은 0~길이 만큼의 배열의 합이다.

array[0] + array[1] -> sum값이고 값은 3이다.

max_sum을 처음의 sum값인 3으로 초기화 해두자.

 

그 후 for문을 길이 ~ 배열의 크기 만큼 돌린다 (길이가2니깐 2부터 ~ 배열의 크기인 5까지)

그리고 sum값을 array[i]에 더하고 sum값을 sum - array[i-length]만큼 뺴주면 된다.

 

계속 서브배열의 합을 구할 필요없어지므로 효과적이게 된다.

---

이 영상을 보는 것을 추천한다!! 

https://www.youtube.com/watch?v=uH9VJRIpIDY