배열을 절반씩 나누면서 탐색 범위를 좁혀가는 방식

초기조건

• 정렬된 배열 혹은 리스트가 필요
• low, mid, hight 3개의 변수 필요

시간복잡도

• O(n) → O(logn)

장점

• 배열의 크기가 커질수록 성능 이점이 커, 큰 데이터셋에서도 빠르게 탐색 가능

단점

• 배열이 정렬되어 있어야만 사용 가능
• 배열의 구조를 변경하거나 삽입/삭제가 잦은 경우 적합하지 않음

1. 정의

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

2. 종류

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

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

3.1 특징

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
    }
}

(1) 탐욕법(그리디) 알고리즘 이란?

매 선택에서 지금 이 순간 최적의 답을 선택하는 알고리즘이다.

단, 매 선택이 각 단계에서는 최적이지만 종합적으로 보았을 경우 최적이라는 보장이 없다.

예를 들어 매 순간 최적을 따라가게되면 1-1-1-100으로 갈경우 매 순간 최적이 아니더라도 1-1-10-10이 종합적으로 보았을 경우 더 최적일 수 있는 경우가 생긴다.

탐욕법(그리디) 알고리즘은 한번의 선택이 다음 선택에는 전혀 무관한 값이여야 하며 매 순간의 최적해가 문제에 대한 최적해인 경우 문제를 해결하는데 강점이있다.