Sliding Window

Sliding Window는 주어진 배열이나 문자열에서 특정 크기의 서브 배열이나 서브 문자열을 연속적으로 처리할 때 사용되는 기법이다. 이 방법은 주로 연속적인 부분에서 계산을 최적화할 때 유용하다. 슬라이딩 윈도우의 주요 아이디어는, 윈도우의 시작점과 끝점을 조정하면서 필요할 때마다 데이터를 업데이트하여 전체 배열을 반복하지 않고도 문제를 해결하는 것이 포인트이다.

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

윈도우 초기화: 처음에 배열의 첫 부분에서 윈도우의 시작점과 끝점을 설정한다.
윈도우 이동: 끝점을 오른쪽으로 이동하면서 새로운 요소를 추가하고, 조건에 따라 시작점을 오른쪽으로 이동한다.
조건 검증: 현재 윈도우의 조건을 검증하고, 필요한 작업(계산, 결과 저장 등)을 수행한다.
반복: 배열 끝까지 윈도우를 이동하면서 작업을 반복한다.

import java.util.*;
import java.io.*;

public class SlidingWindow {
    public static void main(String[] args){
        int k = 3;
        int[] arr ={1,2,3,4,5,6,7,8};
        System.out.println(maxSum(arr,k));
    }

    static int maxSum(int[] arr, int k){
        if(arr.length < k){
            return -1;
        }
        int maxSum = 0;
        int windowSum = 0;

        for(int i = 0; i < k; i++){
            windowSum += arr[i];
        }
        maxSum = windowSum;

        for(int i = 0; i < arr.length; i++){
            windowSum += arr[i] - arr[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

슬라이딩 윈도우

윈도우 정의
- 배열에서 길이가 k인 연속적인 요소들로 이루어진 부분을 윈도우라고 한다.
- 예를 들어, 배열이 [1, 2, 3, 4, 5, 6, 7, 8]이고 k = 3이라면, 초기 윈도우는 [1, 2, 3] 이다.
초기 윈도우의 합
- 처음에 k개의 요소의 합을 구한 후, 그 값을 windowSum에 저장한다.
- 이 예제에서 처음 윈도우는 [1, 2, 3]이고, 그 합은 1 + 2 + 3 = 6 이다.
윈도우 이동
- 윈도우를 한 칸 오른쪽으로 이동시키려면, 새로운 요소를 추가하고, 가장 왼쪽의 요소를 제거해야 한다.
- 예를 들어, 다음 윈도우는 [2, 3, 4] 이다.
- 여기서 4는 새로운 요소로 추가되고, 1은 윈도우에서 나가게 된다.
합 계산
- windowSum += arr[i] - arr[i - k]; 이 부분이 바로 이 과정을 수행한다.
- arr[i]는 새로운 요소(현재 인덱스 i의 값)를 의미하고, arr[i - k]는 윈도우에서 제거될 요소(윈도우의 가장 왼쪽 요소)를 의미한다.
- 예를 들어, 윈도우를 [1, 2, 3]에서 [2, 3, 4]로 이동할 때
  - windowSum은 6 (이전 합)에서 1 (나간 요소)을 빼고 4 (새로운 요소)를 더하게 되어
  - windowSum = 6 - 1 + 4 = 9가 된다.
  - windowSum += arr[i] - arr[i - k];*는 현재 윈도우의 합을 효율적으로 업데이트하는 방법이다.
  - 이 코드를 사용하면 매번 새로운 윈도우의 합을 모두 더하지 않고도, 단 두 개의 값만으로 윈도우의 합을 빠르게 계산할 수 있다.

Reference

https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples