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

알고리즘에 대한 이해 !

'슬라이딩 윈도우'란 ?

슬라이딩 윈도우라는 말은 옆으로 '한칸씩 슬라이딩한다 .'라는 말과 배열의 그림이 창문을 모아놓은 것 같아 슬라이딩 윈도우라는 명칭이 되었다고 어디서 들은 것 같아요 !

1차원 배열을 2회 이상 반복적으로 탐색해야 할 경우 O(n^2) 이상이 걸릴 시간 복잡도를 부분 배열을 활용하여 O(n)으로 줄일 수 있는 장점이 있습니다.

부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘 이지만 부분 배열 길이가 고정적입니다.

어떤 창문을 왼쪽부터 오른쪽으로 밀어 오면서 창문 안에 있는 값들을 부분 배열이라고 생각하면 될 것 같습니다 !

0부터 n까지의 배열에서 최대의 합을 찾으려면 아래의 사진과 같이 0~4가지의 합을 먼저 구해 놓은 뒤 5번째 수를 더해주고 0번째 수를 빼주는 식으로 진행할 수 있습니다 !

구현

 public static void main() {
 	int n = 9;
        int m = 5;
        int[] arr = {1, 3, 2,6, -1, 4, 1, 8, 2};
        int answer = 0;
        int sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i];
        answer = sum;
        for(int i = k; i < n; i++){
            sum += (arr[i] - arr[i - k]);
            answer = Math.max(answer, sum);
        }
        System.out.println(answer);
    }