슬라이딩 윈도우 기법

정의

슬라이딩 윈도우는 일정 크기의 ‘윈도우’를 데이터 위에서 이동시키면서 문제를 해결하는 방법. 주로 배열이나 문자열과 같은 선형 데이터 구조에서 사용됩니다.

특징

• 고정 크기의 윈도우를 사용합니다.
• 윈도우를 한 칸씩 이동시키며 데이터를 처리합니다.
• 이전 윈도우의 계산 결과를 활용하여 효율성을 높입니다.

적용 분야

• 연속된 부분 배열의 합 계산
• 문자열 패턴 매칭
• 데이터 스트림에서의 실시간 분석

예시 코드

import java.util.Arrays;

public class SlidingWindowExample {
    public static int[] findMaxSumSubarray(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k <= 0 || k > arr.length) {
            return new int[0];
        }

        int maxSum = 0;
        int windowSum = 0;
        int startIndex = 0;

        // 초기 윈도우의 합 계산
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        maxSum = windowSum;

        // 슬라이딩 윈도우 이동
        for (int i = k; i < arr.length; i++) {
            windowSum = windowSum - arr[i - k] + arr[i];
            if (windowSum > maxSum) {
                maxSum = windowSum;
                startIndex = i - k + 1;
            }
        }

        // 최대 합을 가진 부분 배열 반환
        return Arrays.copyOfRange(arr, startIndex, startIndex + k);
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 10, 23, 3, 1, 0, 20};
        int k = 4;
        int[] result = findMaxSumSubarray(arr, k);
        System.out.println("최대 합을 가진 부분 배열: " + Arrays.toString(result));
    }
}

코드 설명

1. findMaxSumSubarray 메소드는 입력 배열과 윈도우 크기 k를 받습니다.
2. 먼저 초기 윈도우(처음 k개의 요소)의 합을 계산합니다.
3. 그 다음, 윈도우를 한 칸씩 오른쪽으로 이동하면서
   • 새로 추가되는 요소를 더하고
   • 제거되는 요소를 뺍니다.
4. 각 단계에서 현재 윈도우의 합이 지금까지의 최대 합보다 크면 최대 합을 갱신합니다.
5. 최종적으로 최대 합을 가진 부분 배열을 반환합니다.

시간 복잡도는 O(n) 여기서 n은 배열의 길이.