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

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

동작방식

일정 정수로 이루어진 배열 int[] arr= {3,1,5,3,4,1,5,7,5,1,8} 가 있다면, 길이가 5인 배열의 합계가 가장 큰 것은 무엇인가? 라는 문제에 사용될 수 있습니다. 일반적으로 아래와 같이 0번째 부터 4번째 (길이가 5이므로) 합을 구하고 저장합니다. 그리고 1번째 부터 5번째까지의 합을 구하고 저장후 처음에 구했던 값과 비교를 하여 큰것을 가지고 있습니다. 이렇게 반복을 하면 됩니다. 하지만 이 방법은 매번 for 루프로 모든 배열의 요소를 지정된 길이만큼 순회하며 합계를 구해 최대값을 구해야하므로 비효율적 입니다.

[3,1,5,3,4],1,5,7,5,1,8 ==> 합: 16, 최대값: 16
3,[1,5,3,4,1],5,7,5,1,8 ==> 합: 14, 최대값: 16
3,1,[5,3,4,1,5],7,5,1,8 ==> 합: 18, 최대값: 18 
...
==> 비효율적

이것을 간단히 생각해보면 처음에 해당 길이만큼 합계를 구하는 것은 어쩔수 없습니다. 하지만, 그 이후부터 매번 돌지 않고 인덱스 1~5까지의 합은 처음에 길했던 0~4까지의 합계에 0번째 배열의 값을 빼고, 5번째 배열의 값을 더한 값과 같습니다. 바로 이 부분에서 처음 구했던 0~4까지의 합계를 재사용하며 다음값을 구할 수 있는데, 이것이 슬라이딩 윈도우 알고리즘의 핵심입니다.

참고사이트

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

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

기본코드

위 설명의 예제를 구현한 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class SlidingWindow_example {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    

    static int[] arr= {3,1,5,3,4,1,5,7,5,1,8};
    static int n;

    static int getFive(int index)
    {
        int sum= 0;
        for (int i = 0; i<5; i++) {
            sum += arr[i + index];
        }
        return sum;
    }

    public static void main(String[] args) throws IOException {        

        n = arr.length;
        int max = -9999;

        int sum = getFive(0);

        for (int i = 0; i <= n - 5; i++) {
            if (sum > max) max = sum;

            // 마지막순간에는 다음 것을 준비할 필요 없음
            if (i == n - 5) break;

            // 다음 것을 준비
            sum += arr[i + 5];
            sum -= arr[i];
        }

        System.out.println(max);

        bw.close();
        br.close();
    }        
}

결과는 26이 나옵니다.