[JAVA/알고리즘] 윈도우 슬라이딩 알고리즘

안녕하세요.

윈도우 슬라이딩 알고리즘에 대해 글을 쓰겠습니다.

이 알고리즘은 배열이나 리스트와 같은 연속된 데이터에 대해 특정 범위의 데이터를 효율적으로 처리하는 데 매우 유용합니다.

윈도우 슬라이딩 알고리즘의 개념

윈도우 슬라이딩 알고리즘은 '윈도우' 라 불리는 고정된 크기의 부분 배열이나 서브리스트를 사용하여 연속된 데이터의 지합을 효율적으로 분석하는 방법 입니다. 이 '윈도우'는 데이터 집합을 순회하면서 한 단계씩'슬라이드' 하며, 각 단계에서 필요한 계산을 수행합니다.

 

알고리즘의 장점

• 효율성 : 윈도우 슬라이딩 알고리즘은 반복적인 계산을 줄여줍니다. 윈도우가 슬라이드 할때 마다 전체를 재계산하는 대신, 윈도의 경계에 있는 요소만을 처리합니다.
• 시간 복잡도 감소 : 많은 문제에서 O(n²) 의 시간복잡도를 가진 알고리즘을 O(n) 으로 최적화 할수 있습니다.

예제(java)

문제: 주어진 배열에서 크기가 k인 연속된 서브 배열의 합계를 찾습니다.

public class SlidingWindowAlgorithm {
    public static int findMaxSum(int[] arr, int k) {
        int maxSum = 0;
        int windowSum = 0;

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

        // 윈도우 슬라이딩
        for (int i = k; i < arr.length; 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("Maximum sum of a subarray of size K: " + findMaxSum(arr, k));
    }
}

코드 설명

1. 초기 윈도우 설정: 첫 'k' 요소의 합을 계산하여 초기 윈도우를 설정합니다.
2. 윈도우 슬라이딩 : 윈도우를 한 요소씩 오른쪽으로 이동합니다. 이때 새로운 요소를 추가하고 , 윈도의 맨 왼쪽 요소를 제거합니다.
3. 최대 합계 업데이트 : 각 슬라이딩 단계에 최대 합계를 업데이트 합니다.

성능

• 시간 복잡도 : O(n) 배열을 한 번만 순회합니다.
• 공간 복잡도 : O(1) 추가적인 공간을 사용하지 않습니다.

 

반복된 계산을 최소화하며 연속된 데이터 집합을 효율적으로 처리할 수 있게 해줍니다.