매개 변수 탐색

"X가 가능한가?"로 바꿔 답 자체를 이분 탐색한다.

골드 III

선수 지식: 이분 탐색

1강 답을 이분 탐색하기 공식

어떤 문제를 푸는가

"가능한 최댓값/최솟값은 얼마인가?" 형태의 최적화 문제를, "값 $$X$$ 가 가능한가?"
라는 예/아니오 판정 문제로 바꿔 그 답 자체를 이분 탐색하는 기법입니다.
매개 변수 탐색(parametric search), 흔히 "답에 대한 이분 탐색"이라 부릅니다.

예: "전선 $$K$$ 개를 길이 $$X$$ 씩 자를 수 있는가?", " $$M$$ 개 공유기를 최소 간격 $$X$$
이상으로 놓을 수 있는가?" — 직접 최적값을 구하긴 어렵지만, 특정 $$X$$ 의 가능
여부는 쉽게 판정할 수 있습니다.

성립 조건 — 단조성(monotonicity)

이 기법이 통하려면 판정 함수 feasible(X)가 단조 여야 합니다.

$\text{어떤 } X_0 \text{에서 } \text{feasible 가 } \text{거짓→참(또는 참→거짓)으로 한 번만 바뀐다}$

예를 들어 "길이 $$X$$ 이하로 자르기가 가능"이 어떤 경계 아래에서는 항상 참,
위에서는 항상 거짓이면, 그 경계를 이분 탐색으로 찾을 수 있습니다.

직관: $$X$$ 가 작을수록(또는 클수록) 조건을 만족하기 쉬워지는 구조가 있어야
합니다. 이 단조성이 없으면 이분 탐색이 엉뚱한 곳에 수렴합니다.

절차

답이 들어 있는 탐색 범위 $$[lo, hi]$$ 를 잡는다.
중간값 $$mid$$ 에 대해 feasible(mid)를 판정한다.
참이면 더 좋은 쪽으로(예: 최댓값을 찾으면 $$lo = mid$$ ), 거짓이면 반대쪽으로
범위를 좁힌다.
범위가 한 점으로 수렴할 때까지 반복.

복잡도

판정 한 번이 $$O(C)$$ , 탐색 범위가 $$R$$ 이면

$O(C \cdot \log R)$

직접 최적화가 $O(C \cdot R)$ 이나 더 나쁜 것을 $\log R$ 배로 줄여 줍니다.
$$R$$ 이 $$10^9$$ 이라도 약 30번 판정이면 충분합니다.

핵심 사고법

문제를 보고 "이 양을 직접 구하긴 어려운데, 특정 값으로 충분/가능한지 판정
하기는 쉽지 않은가?"를 자문하세요. 그 질문에 "예"라면 매개 변수 탐색의
신호입니다. 어려운 최적화를 쉬운 판정으로 바꾸는 발상의 전환이 본질입니다.
다음 강의에서 정수/실수 구현과 경계 처리를 봅니다.

2강 매개 변수 탐색 구현과 경계 공식

정수 답 — 최댓값 찾기 (C++)

"조건을 만족하는 가장 큰 $$X$$ "를 찾는 골격입니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 길이 X로 잘랐을 때 만든 도막 수가 K개 이상인가?
bool feasible(vector<ll>& a, ll X, ll K) {
    if (X == 0) return true;
    ll cnt = 0;
    for (ll x : a) cnt += x / X;
    return cnt >= K;
}

int main() {
    int n; ll K; cin >> n >> K;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;

    ll lo = 0, hi = *max_element(a.begin(), a.end());
    while (lo < hi) {
        ll mid = lo + (hi - lo + 1) / 2;     // 위로 올림: 최댓값 탐색
        if (feasible(a, mid, K)) lo = mid;   // 가능하면 더 크게
        else hi = mid - 1;                   // 불가능하면 줄인다
    }
    cout << lo << '\n';
}

mid 올림 (hi - lo + 1)/2가 핵심입니다. 최댓값을 찾을 때
mid = (lo+hi)/2로 내림하면 lo = mid에서 무한 루프에 빠집니다.

최솟값 찾기 골격

"조건을 만족하는 가장 작은 $$X$$ "는 방향을 뒤집습니다.

while (lo < hi) {
    ll mid = lo + (hi - lo) / 2;       // 내림
    if (feasible(mid)) hi = mid;       // 가능하면 더 작게
    else lo = mid + 1;                 // 불가능하면 키운다
}
// lo == hi 가 답

실수 답 — 횟수 고정 이분 탐색

실수 답은 "lo < hi" 대신 충분히 많은 반복 으로 정밀도를 맞춥니다.

double lo = 0, hi = 1e9;
for (int iter = 0; iter < 100; iter++) {   // 100번이면 충분히 정밀
    double mid = (lo + hi) / 2;
    if (feasible(mid)) lo = mid;
    else hi = mid;
}
// lo(또는 hi)가 답

while (hi - lo > eps)도 가능하지만, 고정 횟수가 부동소수 정체 위험이 없어
더 안전합니다.

파이썬 (정수, 최댓값)

import sys
input = sys.stdin.readline

def feasible(a, X, K):
    if X == 0:
        return True
    return sum(x // X for x in a) >= K

n, K = map(int, input().split())
a = [int(input()) for _ in range(n)]
lo, hi = 0, max(a)
while lo < hi:
    mid = (lo + hi + 1) // 2          # 올림
    if feasible(a, mid, K):
        lo = mid
    else:
        hi = mid - 1
print(lo)

흔한 함정

무한 루프 — 최댓값 탐색에서 mid 올림을 잊으면 lo = mid가 진전 없이
반복됩니다. 이 단원의 1순위 버그.
단조성 미확인 — 판정이 단조가 아니면 이분 탐색 자체가 틀립니다. 먼저
단조성을 논증하세요.
탐색 범위 설정 — hi를 너무 작게 잡으면 답을 놓칩니다. 이론적 상한을
넉넉히.
오버플로 — 판정 함수 내부의 합이 클 수 있으므로 long long.
mid 오버플로 — (lo + hi) / 2 대신 lo + (hi - lo) / 2.

응용 패턴

자르기/배치 문제 — 랜선 자르기, 공유기 설치, 나무 자르기.
최소화의 최대 / 최대화의 최소 — "가장 긴 구간을 최소화" 류.
k번째 값 — "X 이하인 원소가 k개 이상인가"로 판정.
시간/속도 최적화 — "T 시간 안에 끝낼 수 있는가".

"최적화를 판정으로, 판정을 이분 탐색으로"라는 한 문장이 이 단원의 전부입니다.
단조성 확인과 경계 처리만 정확하면 광범위한 문제에 곧장 적용됩니다.

3강 실전 가이드 — '최솟값의 최댓값'을 보는 눈 공식

출제 신호

매개 변수 탐색(파라메트릭 서치)의 신호 문구는 정형화되어 있습니다.

"가장 가까운 두 ○○ 사이 거리의 최댓값" (공유기 설치류) —
"최솟값을 최대화"
"가장 큰 묶음의 크기를 최소화" (구간 나누기류) — "최댓값을 최소화"
"랜선을 똑같이 잘라 $$N$$ 개 이상 만들 수 있는 최대 길이",
"나무를 잘라 $$M$$ 미터 이상 가져가는 최대 절단 높이"
"조건을 만족하는 최소 시간/최소 용량/최대 크기" + 답의 범위가
$10^{18}$ 급으로 거대해서 답을 직접 계산할 수 없을 때

공통 구조: 답 $$x$$ 에 대해 결정 문제 " $$x$$ 로 가능한가?"가 한쪽 방향으로
단조입니다(가능하다가 어느 지점부터 불가능, 혹은 그 반대). 단조성이
확인되면 답의 구간을 이분 탐색합니다.

풀이 결정 절차

결정 함수 ok(x)를 문장으로 적습니다 — "절단 높이 $$x$$ 일 때 가져가는
양이 $$M$$ 이상인가?"
단조성 증명을 한 줄로 — " $$x$$ 를 줄이면 가져가는 양은 늘어난다" 같은
방향 논증이 안 되면 매개 변수 탐색이 아닙니다.
ok(x) 한 번의 비용을 확인합니다 — 보통 $$O(N)$$ 탐욕/시뮬레이션.
전체는 $O(N \log(\text{답 범위}))$ .
답의 하한 lo / 상한 hi를 안전하게 잡습니다 — hi는 "확실히 되는(또는
안 되는) 극단값"으로 넉넉히.
"가능한 것 중 최대"인지 "가능한 것 중 최소"인지에 따라 어느 쪽 경계를
당길지 정합니다.

자주 하는 실수

무한 루프 — while (lo < hi)에서 최대화를 할 때
mid = (lo + hi) / 2; lo = mid;로 쓰면 hi = lo + 1에서 영원히 멈추지
않습니다. 최대화는 mid를 올림으로 잡아야 합니다.

// "가능한 최대 x" 패턴
while (lo < hi) {
    long long mid = (lo + hi + 1) / 2;   // 올림 — lo = mid 와 한 쌍
    if (ok(mid)) lo = mid;               // 가능하면 더 키워 본다
    else hi = mid - 1;
}
// 종료 시 lo == hi 가 답

// "가능한 최소 x" 패턴
while (lo < hi) {
    long long mid = (lo + hi) / 2;       // 내림 — hi = mid 와 한 쌍
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
}

mid 오버플로 — lo + hi가 $10^{18}$ 급이면 C++에서 넘칠 수 있습니다.
lo + (hi - lo) / 2 또는 처음부터 unsigned/범위 점검.
결정 함수 안의 조기 오버플로 — "자른 양의 합"이 long long을 넘기 전에
$$M$$ 이상이면 바로 return true로 끊는 방어가 필요할 때가 있습니다.
경계 포함 실수 — lo를 0부터 시작해야 하는지 1부터인지(길이 0이
허용되는가), hi가 답이 될 수 있는지 — 끝에서 한 칸 차이로 틀리는 문제가
많으니 lo, hi 초기값이 모두 "후보로서 유효한지" 점검하세요.
단조성 미확인 — ok가 단조가 아닌데 이분 탐색을 돌리면 그럴듯한
오답이 나옵니다. 반례를 하나 만들어 보는 게 증명 다음으로 좋은 방어입니다.

연습 방법

사이드바 연습 목록의 랜선/나무 자르기류(최대화)와 구간 나누기류(최소화)를
짝으로 풀어 두 패턴(올림 mid vs 내림 mid)을 손에 새기세요. 매 문제에서
ok(x)의 정의와 단조 방향을 주석 첫 줄에 적는 습관을 들이면 경계 실수가
급감합니다. 태그된 문제 3문제 이상 해결 시 마스터 처리되어 레이팅
CLASS 보너스에 반영됩니다.