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

💡 슬라이딩 윈도우(Sliding window)란?

슬라이딩 윈도우는 배열에서 하나의 틀(부분 배열)을 일정한 크기 만큼 이동시키며 문제를 풀이하는 알고리즘이다. 공통된 부분은 유지하고, 새로 추가되거나 삭제된 부분의 데이터만 갱신하여 문제를 해결하기 때문에, 시간복잡도를 줄일 수 있다.

투포인터 알고리즘과의 차이점

슬라이딩 윈도우와 비슷한 것이 바로 투포인터 알고리즘이다. 둘 다 배열을 일정 크기만큼 이동하며 문제를 풀이하는 알고리즘이고, 공통된 부분을 재사용한다는 공통점이 있다.

이 두 알고리즘의 차이점은 바로 틀 길이의 변화 여부이다. 슬라이딩 윈도우 알고리즘은 틀(부분 배열)의 크기가 고정되어있는 반면, 투포인터 알고리즘은 틀의 길이가 가변적이다.

이런 틀의 특성때문에 코드에도 차이가 생긴다. 슬라이딩 윈도우 알고리즘 틀의 길이를 알고 있기 때문에 변수 하나를 가지고 코드를 짜지만, 투포인터 알고리즘은 시작점과 끝점을 알려줄 변수 두 가지를 가지고 코드를 작성한다.

문제 풀이

백준 2559

일정한 길이만큼 한칸씩 옆으로 이동하기 때문에, 슬라이딩 윈도우 알고리즘을 적용할 수 있다.

        for(int i=0;i<n+1-k;i++){
            tmp=0;
            for(int j=0;j<k;j++){
                tmp+=temperatureList.get(i+j);
            }
            if(i==0) max=tmp;
            if(tmp>max) max=tmp;
        }
        bw.write(max+"");

슬라이딩 알고리즘을 적용하기 전 코드이다. 합을 계산하여 최댓값과 비교할 때 이중 for문을 사용했기 때문에, 실행 시간이 오래걸릴수밖에 없었다.

		long max = 0, sum;
        for(int i=0;i<k;i++){
            max+=temperatureList.get(i);
        }

        sum=max;
        int start=0;
        int end=k;

        while(end<n){
            sum = sum-temperatureList.get(start)+temperatureList.get(end);
            max=Math.max(max, sum);
            start+=1;
            end+=1;
        }

슬라이딩 윈도우 알고리즘을 적용한 코드이다. 첫 max를 구하기 위해 따로 for문을 돌려주었고, 그 뒤로는 반복된 부분을 이용하여 문제를 풀었다.

 		long max = 0, sum;
        for(int i=0;i<k;i++){
            max+=temperatureList.get(i);
        }

        sum=max;
        int end=k;

        while(end<n){
            sum = sum-temperatureList.get(end-k)+temperatureList.get(end);
            max=Math.max(max, sum);
            end+=1;
        }

고정된 길이이기 때문에 start변수 필요 없이, 변수 하나만으로 계산이 가능하다.

이중 for문 대신에 슬라이딩 윈도우를 적용함으로써 눈에띄게 실행 시간을 줄일 수 있었다.

정리

• 슬라이딩 윈도우는 부분합 연산에 주로 사용된다.
• 슬라이딩 윈도우는 고정적인 범위를 탐색할 때 유용하다.
• 슬라이딩 윈도우를 사용하면 중복 연산을 제거해 코드의 효율을 높일 수 있다.