매개변수 탐색

최적화 문제(최솟값/최댓값을 찾는 문제)를 "답이 X 이하로 가능한가?"라는 결정 문제로 바꾸고, 그 답의 범위를 이진 탐색으로 좁혀가며 푸는 기법입니다.

동작 과정

문제: 배열을 K개의 연속 구간으로 나눌 때, 각 구간 합 중 최댓값을 최소로 만들기.

A = [7, 2, 5, 10, 8]   K = 2

답의 하한 = max(A) = 10   (한 구간에 가장 큰 원소 하나는 반드시 들어가야 함)
답의 상한 = sum(A) = 32   (구간을 1개로 묶은 경우)

feasible(mid): "구간 합이 mid를 넘지 않게 묶을 때 필요한 구간 수 ≤ K?"
  그리디로 앞에서부터 채우다가 mid를 넘기 직전에 구간을 자른다.

lo=10, hi=32
  mid=21 → [7,2,5 | 10,8]      2구간, 2≤2 → feasible   → hi=21
  mid=15 → [7,2,5 | 10 | 8]    3구간, 3>2 → infeasible  → lo=16
  mid=18 → [7,2,5 | 10,8]      2구간, 2≤2 → feasible   → hi=18
  mid=17 → [7,2,5 | 10 | 8]    3구간, 3>2 → infeasible  → lo=18

lo == hi == 18 → 답 = 18
  (실제로 [7,2,5|10,8] → 합 14, 18 → 최댓값 18이 가능한 최소값)

구간 자체를 탐색하는 것이 아니라 "답이 될 수 있는 값의 범위"를 탐색 대상으로 삼기 때문에, 배열 인덱스 대신 답의 하한~상한을 lo, hi로 둡니다.

구현

int minimizeLargestSum(int[] a, int k) {
    int lo = 0, hi = 0;
    for (int x : a) {
        lo = Math.max(lo, x);   // 하한: 가장 큰 원소
        hi += x;                // 상한: 전체 합
    }

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(a, k, mid)) {
            hi = mid;           // mid로도 가능 → 더 작은 값을 시도
        } else {
            lo = mid + 1;       // mid로는 불가능 → 더 큰 값 필요
        }
    }
    return lo;
}

// 구간 합이 limit를 넘지 않게 묶을 때 필요한 구간 수가 k 이하인가
boolean feasible(int[] a, int k, int limit) {
    int count = 1, curr = 0;
    for (int x : a) {
        if (curr + x > limit) {
            count++;
            curr = 0;
        }
        curr += x;
    }
    return count <= k;
}

feasible 하나만 문제에 맞게 바꾸면 "공유기 최대 간격 최대화", "작업 분배 시간 최소화" 같은 다른 최적화 문제에도 같은 틀을 그대로 적용할 수 있습니다.

복잡도

구분복잡도근거
시간O(N log(답의 범위))이진 탐색 O(log(hi-lo))마다 feasible 검사 O(N)
공간O(1)feasible 검사가 추가 메모리 없이 선형으로 끝나는 경우

feasible 자체가 O(N)보다 비싸면(예: 내부에 또 다른 루프나 자료구조가 있으면) 전체 시간복잡도는 그만큼 늘어납니다.

주의사항

핵심 정리

CSLOG에서 보기