매개 변수 탐색 (Parametric Search)

정의

매개 변수 탐색 (Parametric Search) 은 답 자체를 이분 탐색하는 기법. “조건을 만족하는 최소값 / 최대값” 문제에서, 조건 만족 여부가 단조성 (monotonicity) 을 가지면 O(log (hi - lo)) 에 최적해를 찾는다.

배열에서 값을 찾는 Binary Search 이 아니라, “k 가 가능한가?” 를 판별하는 함수 f(k) 가 단조 증가 / 감소할 때 적용.

문제 상황과 동기

최적화 문제에서 답 후보 범위가 [lo, hi] 로 정해져 있고, 답을 직접 계산하기 어렵지만 “k 가 답이 될 수 있는가?” 는 O(g(N)) 으로 판별 가능한 상황.

• naive: lo 부터 hi 까지 모두 시도. O((hi - lo) × g(N)).
• parametric search: f(k) = (k 가 가능?) 이 단조이면, k 를 이분 탐색. O(log (hi - lo) × g(N)).

예: “N 개 랜선을 K 개로 자를 수 있는 최대 길이?” → f(len) = (len 으로 K 개 이상 가능?) 는 len 이 커질수록 false. 최대 가능 len 을 이분 탐색.

핵심 통찰: “답에 대한 조건이 단조” 면 답 공간을 이분 탐색 가능.

시각화

핵심 아이디어

invariant: f(k) 는 단조 (false…false true…true 또는 true…true false…false).

초기: lo = 가능한 최소 후보, hi = 가능한 최대 후보 + 1
while lo < hi:
    mid = lo + (hi - lo) / 2
    if f(mid):  # mid 가 조건 만족 (예: 최소값 구하기)
        hi = mid     # mid 는 가능, 더 작은 값도 시도
    else:
        lo = mid + 1
return lo  # 가장 작은 가능 값

최대값 구하기는 조건 반대로:

while lo < hi:
    mid = lo + (hi - lo + 1) / 2  # 올림
    if f(mid):
        lo = mid     # mid 가능, 더 큰 값도 시도
    else:
        hi = mid - 1
return lo

매 단계마다 답 후보 절반 제거.

알고리즘

최소값 찾기 (f(k): k 이상이면 가능)

parametric_min(lo, hi, f):
    # f(k) = (k 가 답으로 가능한가?)
    # false...false true...true 형태
    while lo < hi:
        mid = lo + (hi - lo) / 2
        if f(mid):  hi = mid
        else:       lo = mid + 1
    return lo

최대값 찾기 (f(k): k 이하면 가능)

parametric_max(lo, hi, f):
    # f(k) = true...true false...false 형태
    while lo < hi:
        mid = lo + (hi - lo + 1) / 2  # 올림으로 무한루프 방지
        if f(mid):  lo = mid
        else:       hi = mid - 1
    return lo

실수 답 (고정 반복)

parametric_real(lo, hi, f):
    for _ in range(100):  # 충분한 정밀도
        mid = (lo + hi) / 2
        if f(mid):  hi = mid
        else:       lo = mid
    return lo

구현

// 랜선 자르기: N 개를 len 으로 잘라 K 개 이상 가능한 최대 len
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k;
  cin >> n >> k;
  vector<long long> a(n);
  for (auto& v : a) cin >> v;
  long long lo = 1, hi = *max_element(a.begin(), a.end()) + 1;
  auto f = [&](long long len) {
      long long cnt = 0;
      for (auto x : a) cnt += x / len;
      return cnt >= k;
  };
  while (lo < hi) {
      long long mid = lo + (hi - lo + 1) / 2;  // 올림
      if (f(mid)) lo = mid;
      else        hi = mid - 1;
  }
  cout << lo << "\n";
}

# 랜선 자르기: N 개를 len 으로 잘라 K 개 이상 가능한 최대 len
import sys
input = sys.stdin.readline
​
n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
​
def f(length):
  return sum(x // length for x in a) >= k
​
lo, hi = 1, max(a) + 1
while lo < hi:
  mid = (lo + hi + 1) // 2
  if f(mid):
      lo = mid
  else:
      hi = mid - 1
print(lo)

// 랜선 자르기: N 개를 len 으로 잘라 K 개 이상 가능한 최대 len
import java.util.*;
import java.io.*;
public class Main {
  static int n, k;
  static long[] a;
  static boolean f(long len) {
      long cnt = 0;
      for (long x : a) cnt += x / len;
      return cnt >= k;
  }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      String[] inp = br.readLine().split(" ");
      n = Integer.parseInt(inp[0]);
      k = Integer.parseInt(inp[1]);
      a = new long[n];
      long maxV = 0;
      for (int i = 0; i < n; i++) {
          a[i] = Long.parseLong(br.readLine().trim());
          maxV = Math.max(maxV, a[i]);
      }
      long lo = 1, hi = maxV + 1;
      while (lo < hi) {
          long mid = lo + (hi - lo + 1) / 2;
          if (f(mid)) lo = mid;
          else        hi = mid - 1;
      }
      System.out.println(lo);
  }
}

4 11
802
743
457
539

200

1 5
1000

200

복잡도

hi - lo = 10^9 이어도 약 30 회 f(k) 호출로 끝.

변형 / 활용

함정

1. 단조성 검증 누락

f(k) 가 단조가 아니면 틀린 답. 예: “합이 정확히 K” 는 단조가 아님 (K-1, K, K+1 모두 false 가능).

2. lo, hi 초기값 실수

lo 는 가능한 최소값 이하, hi 는 가능한 최대값 초과 로 잡아야 안전.

// 잘못: hi = max(a)  -> 답이 max(a) 일 때 누락
// 올바름: hi = max(a) + 1

3. mid 계산 올림 / 내림

최대값 찾기는 mid = (lo + hi + 1) / 2 (올림), 아니면 무한 루프.

// 잘못: lo = 3, hi = 4 -> mid = 3 -> lo = 3 (무한)
// 올바름: mid = (3 + 4 + 1) / 2 = 4

4. f(k) 오버플로우

k 를 long long 으로, 중간 계산도 주의.

// 잘못: int cnt = (int)x / len; cnt += ...
// 올바름: long long cnt = 0; cnt += x / len;

실전 패턴

BOJ 연습 문제

참고

• Binary Search
• Ternary Search
• Aliens Trick (lambda 에 대한 parametric search)