슬라이딩 윈도우 알고리즘

해당 포스트는 이지스퍼블리싱, 『알고리즘 코딩테스트 자바 편』, Gene 김종관 을 참고하여 작성하였습니다.

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

슬라이딩 윈도우 알고리즘은 고정 크기의 윈도우를 가지고 이를 이동시키면서 문제를 해결하는 알고리즘입니다. 주로 연속된 구간을 탐색하거나 구간 내의 최소/최대 값을 찾을 때 사용됩니다. 윈도우의 크기는 문제의 조건에 따라 다르게 설정될 수 있습니다.

슬라이딩 윈도우 알고리즘의 접근 방법

1. 윈도우 초기화: 알고리즘을 시작하기 전에 고정 크기의 윈도우를 설정하고 윈도우의 내부 상태를 초기화합니다.
2. 윈도우 이동: 윈도우를 한 칸씩 이동시키면서 구간을 탐색하거나 특정 작업을 수행합니다.
3. 조건 검사: 윈도우 내의 구간을 조건에 따라 검사하고 필요한 작업을 수행합니다.
4. 윈도우 크기 유지: 문제에 따라 윈도우의 크기를 유지하거나 변경합니다. 윈도우를 이동시키면서 새로운 요소를 추가하고 이전 요소를 제거합니다.
5. 윈도우 이동 및 반복: 윈도우를 이동시키고 다시 조건을 검사하여 필요한 작업을 수행합니다. 문제의 조건을 만족하는 결과를 찾을 때까지 반복합니다.

예시 코드

아래는 슬라이딩 윈도우 알고리즘을 사용하여 배열에서 고정 크기의 윈도우를 이동시키면서 윈도우 내의 합이 최대가 되는 값을 찾는 예시 코드입니다.

public class SlidingWindowExample {
    public static int maxSumInWindow(int[] nums, int k) {
        int maxSum = 0;
        int windowSum = 0;

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

        // 윈도우 이동 및 최대 합 계산
        for (int i = k; i < nums.length; i++) {
            // 새로운 요소 추가 및 이전 요소 제거
            windowSum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int maxSum = maxSumInWindow(nums, k);
        System.out.println("윈도우 내의 최대 합: " + maxSum);
    }
}

위의 코드에서 maxSumInWindow 메서드는 배열 nums에서 고정 크기 k의 윈도우를 이동시키면서 윈도우 내의 합이 최대가 되는 값을 찾습니다. 윈도우를 이동시키면서 새로운 요소를 추가하고 이전 요소를 제거하여 윈도우 내의 합을 계산하고, 최대 합을 업데이트합니다.