유형별 정리/탐색 기법
탐색 기법O(n log(범위))

파라메트릭 서치 — 결정 문제로 바꾸기

"최댓값?"을 "이 값으로 가능해?"로 바꿔 답 자체를 이분탐색해요. 랜선 자르기의 정석이에요.

이럴 때 써요

  • "최대 길이", "최소 시간", "가능한 가장 큰 값"처럼 최적값을 묻는 문제
  • 값을 하나 정해주면 "그 값으로 되나 안 되나"를 쉽게 판정할 수 있을 때
  • 판정 결과가 어느 지점을 기준으로 참→거짓(또는 거짓→참)으로 딱 갈릴 때 (단조)
  • 답의 후보 범위는 넓은데(예: 1 ~ 10억) 하나씩 다 넣어보긴 너무 많을 때

개념

"랜선을 최대 몇 cm로 자를 수 있을까?" 같은 문제는 답을 바로 구하기 어려워요. 그런데 질문을 뒤집어 "길이 x로 자르면 K개 이상 나와?"라고 물으면 세어보기만 하면 되니 훨씬 쉬워요. 이렇게 최적화 문제를 결정(판정) 문제 possible(x)로 바꾸는 게 파라메트릭 서치의 핵심이에요.왜 이분탐색이 되냐면, 판정 함수가 단조라서예요. 길이가 짧을수록 조각은 많이 나오니까, x를 키우면 어느 지점까진 계속 가능이다가 그 뒤론 쭉 불가능이에요. 참과 거짓이 딱 한 번만 갈리니, 그 경계를 값의 범위 [lo, hi]에서 이분탐색으로 찾으면 돼요. x를 하나씩 다 넣는 대신 log(범위)번이면 끝나요.
"랜선 [802, 743, 457, 539], K=11개, 길이 x는?" — possible(x)로 좁히기
possible(x): 각 랜선을 x로 자른 조각 수 합이 11 이상이면 참
답의 범위: lo=1, hi=802 (가장 긴 랜선)
​
lo=1, hi=802  →  mid=401  조각=2+1+1+1=5  <11  불가능  →  hi=400
lo=1, hi=400  →  mid=200  조각=4+3+2+2=11 >=11  가능    →  기록 200, lo=201
lo=201,hi=400 →  mid=300  조각=2+2+1+1=6  <11  불가능  →  hi=299
lo=201,hi=299 →  mid=250  조각=3+2+1+2=8  <11  불가능  →  hi=249
... lo가 hi를 넘으면 종료, 마지막으로 가능했던 200이 답
"최대"를 찾을 땐 판정이 성공한 값을 답으로 기록하면서 위로 밀어요 (lo = mid + 1). 성공했으니 더 큰 값도 되는지 욕심내 보는 거예요. 반대로 "최소"를 찾을 땐 성공한 값을 기록하고 아래로 밀어요 (hi = mid - 1). 어느 쪽이든 "성공하면 기록하고 그 방향으로 더 간다"가 요령이에요.

패턴 코드

파라메트릭 서치 틀 — 랜선 자르기(길이 x의 최댓값)possible(x)는 길이 x로 잘랐을 때 조각이 k개 이상인지 판정해요. 성공하면 답을 기록하고 lo를 위로 밀어 더 큰 길이에 도전해요.
javascript
function maxCableLength(cables, k) {
  const possible = (x) => {
    let count = 0;
    for (const c of cables) count += Math.floor(c / x);
    return count >= k;
  };
  let lo = 1;
  let hi = Math.max(...cables);
  let answer = 0;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (possible(mid)) {
      answer = mid;   // 성공: 기록하고 더 크게
      lo = mid + 1;
    } else {
      hi = mid - 1;   // 실패: 더 작게
    }
  }
  return answer;
}

이 유형으로 풀어보기

← 이분탐색 — 값·경계 찾기슬라이딩 윈도우 →