슬라이딩 윈도우 알고리즘에 관하여

슬라이딩 윈도우(Sliding Window)는 배열이나 문자열과 같은 데이터 구조에서 특정 조건에 맞는 부분 구간을 효율적으로 탐색하거나 계산하기 위한 알고리즘 기법입니다. 이 글에서는 슬라이딩 윈도우 알고리즘의 개념, 작동 원리, 주요 사례 및 구현 방법에 대해 알아보겠습니다.

1. 슬라이딩 윈도우 알고리즘이란?

슬라이딩 윈도우는 고정된 크기의 윈도우(구간)를 데이터 구조 위에서 이동시키며 문제를 해결하는 방식입니다. 반복적으로 윈도우를 이동하면서 이전 계산 결과를 활용하여 효율적인 처리를 제공합니다.

사용 목적

• 불필요한 계산을 줄여 성능 최적화
• 특정 구간 내의 값을 계산하거나 조건을 만족하는 부분을 탐색

2. 작동 원리

슬라이딩 윈도우는 기본적으로 두 개의 포인터(보통 시작 포인터와 끝 포인터)를 사용하여 데이터 구간을 추적합니다. 다음은 작동 흐름입니다:

1. 초기화: 시작 포인터와 끝 포인터를 초기 위치로 설정하고, 초기 값을 계산합니다.
2. 윈도우 확장: 끝 포인터를 이동시켜 윈도우를 확장합니다.
3. 윈도우 축소: 필요에 따라 시작 포인터를 이동시켜 윈도우를 축소합니다.
4. 계산 갱신: 윈도우 이동 시 이전 계산 결과를 기반으로 값을 갱신합니다.

3. 예제

3.1 고정 크기 합 계산

배열의 크기 k인 연속된 부분합을 구합니다.

예제 문제

배열 [1, 3, 2, 6, 2, 8]에서 크기 k = 3인 부분합의 최대값을 구하세요.

구현 코드 (Java)

public class SlidingWindowExample {
    public static int maxSumOfKSubarray(int[] arr, int k) {
        int n = arr.length;
        if (n < k) {
            return -1;
        }

        int maxSum = 0;
        for (int i = 0; i < k; i++) {
            maxSum += arr[i];
        }

        int currentSum = maxSum;
        for (int i = k; i < n; i++) {
            currentSum += arr[i] - arr[i - k];
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 6, 2, 8};
        int k = 3;
        System.out.println(maxSumOfKSubarray(arr, k)); // 출력: 16
    }
}