[Algorithm/Java] 슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우(Sliding Window)란?

슬라이딩 윈도우(Sliding Window) 알고리즘은 배열이나 리스트에서 연속된 부분 구간(윈도우)을 효율적으로 탐색할 때 사용되는 알고리즘이다. 다음과 같은 상황에 자주 활용된다.

• 고정된 크기의 부분 배열을 찾는 문제
• 연속된 부분 구간의 최대값/최소값을 찾는 문제
• 특정 조건을 만족하는 부분 구간을 찾는 문제

슬라이딩 윈도우를 사용하면 고정된 크기의 윈도우를 정해 그 크기 안에서 데이터를 참색하거나 누적 계산을 수한다. 매번 전체 배열을 탐색하는 대신 윈도우를 이동하며 필요한 계산만 업데이트 하므로 시간 복잡도 O(N)이다.

 

배열에서 고정된 크기의 부분합 중 최대값을 구하는 예제를 보자.

public class SlidingWindowExample {
    public static int maxSum(int[] arr, int k) {
        int n = arr.length;
        if (n < k) throw new IllegalArgumentException("윈도우 크기가 배열보다 큽니다.");

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

        int maxSum = windowSum;

        // 윈도우 이동
        for (int i = k; i < n; i++) {
            windowSum += arr[i] - arr[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        int k = 3;
        System.out.println("최대합: " + maxSum(arr, k));
    }
}