Sliding Window 알고리즘

슬라이딩 윈도우 알고리즘은 일반적으로 연속된 부분 배열(또는 문자열)의 최대/최소 값을 찾는 데 사용됩니다. 

이 알고리즘의 기본 아이디어는 매번 모든 값의 합계나 곱을 계산하는 것이 아니라, 이전 연속된 부분 배열의 합계나 곱에서 현재 값과 이전 값의 차이만 계산하여 계산량을 줄이는 것입니다.

 

public static int maxSumSubarray(int[] arr, int k) {
    int n = arr.length;
    int maxSum = Integer.MIN_VALUE;
    int windowSum = 0;
    
    // 슬라이딩 윈도우 시작
    for (int i = 0; i < n - k + 1; i++) {
        // 현재 윈도우의 합을 계산
        for (int j = i; j < i + k; j++) {
            windowSum += arr[j];
        }
        // 이전 윈도우와의 차이 중 최대 값을 찾음
        maxSum = Math.max(maxSum, windowSum);
        // 다음 윈도우의 합을 계산하기 위해 첫 번째 값을 빼고 두 번째 값을 더함
        windowSum -= arr[i];
        windowSum += arr[i + k];
    }
    return maxSum;
}

 

1. 배열 arr와 윈도우 크기 k를 매개변수로 받아서 최대 합계를 구하는 슬라이딩 윈도우 알고리즘을 구현

 

2. 우선 배열 arr의 길이 n을 변수에 저장하고, 최대 합계를 저장할 변수 maxSum과 현재 윈도우의 합계를 저장할 변수 windowSum을 초기화합니다.

3.  슬라이딩 윈도우를 시작합니다. 이를 위해 for 루프를 사용하고, i 변수는 현재 윈도우의 첫 번째 인덱스를 나타냅니다. 이 중첩된 루프에서는 현재 윈도우의 합계를 계산합니다.

4. 이전 윈도우와 현재 윈도우의 합계 중 최대 값을 찾습니다. Math.max() 메소드를 사용하여 이전 maxSum 값과 현재 windowSum 값을 비교하고, 더 큰 값을 maxSum에 할당합니다.

5. 다음 윈도우의 합계를 계산하기 위해, 현재 윈도우에서 첫 번째 값을 제거하고 다음 값을 추가합니다.

 

큐를 사용한 슬라이딩 윈도우

public static int maxSumSubarray(int[] arr, int k) {
    int n = arr.length;
    int maxSum = Integer.MIN_VALUE;
    int windowSum = 0;
    Deque<Integer> window = new LinkedList<>();
    
    // 슬라이딩 윈도우 시작
    for (int i = 0; i < n; i++) {
        // 현재 값을 큐에 추가
        window.add(arr[i]);
        // 현재 윈도우 크기가 k보다 큰 경우 큐에서 첫 번째 값을 제거
        if (window.size() > k) {
            windowSum -= window.remove();
        }
        // 현재 윈도우의 합을 계산
        windowSum += arr[i];
        // 윈도우가 k개의 요소를 포함하는 경우 최대 값을 찾음
        if (window.size() == k) {
            maxSum = Math.max(maxSum, windowSum);
        }
    }
    return maxSum;
}

 

1. 배열 arr와 윈도우 크기 k를 매개변수로 받아서, 최대 합계를 구하는 슬라이딩 윈도우 알고리즘을 큐를 사용하여 구현

2. 우선 배열 arr의 길이 n을 변수에 저장하고, 최대 합계를 저장할 변수 maxSum, 현재 윈도우의 합계를 저장할 변수 windowSum, 그리고 현재 윈도우를 저장할 큐 window을 초기화합니다.

3. 슬라이딩 윈도우를 시작합니다. 이를 위해 for 루프를 사용하고, i 변수는 현재 요소의 인덱스를 나타냅니다. 큐에 현재 값을 추가하고, 큐의 크기가 k보다 큰 경우에는 큐에서 첫 번째 값을 제거합니다.

4. 현재 윈도우의 합계를 계산합니다. 큐에 남아 있는 요소들의 합계를 계산하고, 현재 값을 추가하여 윈도우의 합계를 계산합니다.

5. 윈도우가 k개의 요소를 포함하는 경우 최대 값을 찾습니다. 현재 윈도우의 크기가 k와 같은 경우, 이전에 저장한 최대 값을 사용하여 최대 값을 찾습니다.

이 알고리즘은 배열에서 연속된 k 개의 요소를 가지는 모든 부분 배열의 합계를 계산하지 않고, 슬라이딩 윈도우를 사용하여 구합니다. 큐를 사용하면 윈도우의 첫 번째 요소를 제거하고 마지막 요소를 추가하는 작업을 상수 시간에 수행할 수 있습니다.

 

 

이해를 위한 그림

 예 ) 양의 정수로 구성된 배열 [2, 4, 7, 10, 8, 4]에서 연속된 요소 3개의 합이 가장 큰 값은?

그림출처 : https://imjeongwoo.tistory.com/11