[Algorithm] 슬라이딩 윈도우

1. 정의

슬라이딩 윈도우(Sliding Window)는 배열이나 리스트에서 특정 범위(윈도우)에 대한 계산을 반복적으로 수행해야 할 때 유용한 알고리즘 기법

2. 종류

• 고정 크기 윈도우
  • 주어진 크기의 연속된 구간을 탐색하는 경우
• 가변 크기 윈도우
  • 특정 조건을 만족하는 구간을 탐색하는 경우

3. 슬라이딩 윈도우 vs 투포인터

3.1 특징

	슬라이딩 윈도우	투 포인터
목적	고정되거나 조건에 따라 이동하는 구간(window)을 탐색	두 포인터를 사용해 배열의 특정 조건을 만족하는 값을 탐색
윈도우 크기	고정 또는 가변	일반적으로 가변
주요 동작	윈도우를 한 칸씩 이동하며 필요한 부분만 갱신	두 포인터를 독립적으로 이동하며 구간의 조건을 만족하도록 조정
사용 상황	연속된 구간에 대한 계산이 필요할 때	정렬된 배열에서 특정 조건을 만족하는 값을 찾거나, 구간을 탐색할 때

3.2 공통점

1. 배열이나 리스트에서 효율적으로 탐색
2. O(N)의 시간 복잡도로 문제 해결 가능

3.3 차이점

1. 탐색 구간
   • 슬라이딩 윈도우
     • 연속된 구간을 유지하며 탐색
   • 투 포인터
     • 두 포인터가 독립적으로 움직이며 조건을 만족하도록 탐색.
2. 조건
   • 슬라이딩 윈도우
     • 윈도우 내 값을 반복적으로 갱신
   • 투 포인터
     • 값이나 조건을 만족할 때까지 포인터를 확장/축소.

3.4 선택 조건

• 슬라이딩 윈도우를 선택:
  • 구간 내 합, 곱, 최대/최소값을 반복적으로 계산해야 하는 경우.
  • 문제에서 “연속된 서브배열”이라는 조건이 있는 경우.
    • 예: 크기가 K인 서브배열의 최대합.
• 투 포인터를 선택:
  • 정렬된 배열에서 조건을 만족하는 두 값이나 범위를 찾는 경우.
  • 문제에서 “특정 합”, “차이”, “곱” 등을 만족하는 두 요소를 요구하는 경우.
    • 예: 두 수의 합, 특정 값의 구간 찾기.

4. 예시

4.1 고정 크기 윈도우

import java.util.Arrays;

public class FixedWindowAverage {

    public static double[] findAverages(int[] arr, int k) {
        if (arr.length < k) {
            throw new IllegalArgumentException("Array length must be greater than or equal to k.");
        }

        double[] result = new double[arr.length - k + 1];
        double windowSum = 0;

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

        result[0] = windowSum / k;

        // 슬라이딩 윈도우 이동
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k]; // 새 요소 추가, 오래된 요소 제거
            result[i - k + 1] = windowSum / k; // 평균 계산
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 3;

        double[] averages = findAverages(arr, k);
        System.out.println("크기 " + k + "의 서브배열 평균값: " + Arrays.toString(averages));
        // 출력: [2.0, 3.0, 4.0]
    }
}

4.2 가변 크기 윈도우

public class VariableWindowExample {

    public static int minSubArrayLen(int target, int[] arr) {
        int n = arr.length;
        int left = 0, sum = 0;
        int minLength = Integer.MAX_VALUE;

        for (int right = 0; right < n; right++) {
            sum += arr[right]; // 윈도우 확장

            while (sum >= target) { // 조건 만족 시 윈도우 축소
                minLength = Math.min(minLength, right - left + 1);
                sum -= arr[left];
                left++;
            }
        }

        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 2, 4, 3};
        int target = 7;

        int result = minSubArrayLen(target, arr);
        System.out.println("합이 " + target + " 이상인 가장 짧은 서브배열의 길이: " + result); // 출력: 2
    }
}