케이크를 어느 높이에서 자를까?
디저트 가게 사장님이 진열대에 높이가 제각각인 케이크들을 세워 두었습니다. 손님들을 위한 무료 시식 코너를 만들려고, 절단기 칼날을 어떤 높이 H에 맞춰 케이크들을 한 번에 가로로 자릅니다.
그러면 H보다 높은 케이크는 윗부분이 잘려 나가고, 그 잘린 윗부분을 모두 모아 시식용 조각으로 씁니다. 핵심은 이겁니다 — 칼날을 낮출수록 더 많이 잘려 시식량은 늘지만, 진열용 케이크가 그만큼 망가집니다.
그래서 시식에 필요한 양은 딱 채우되, 진열 손상을 최소화하도록 칼날을 최대한 높게 두는 게 목표예요.
예: 케이크 높이가 15, 22, 9, 18, 30, 25이고 시식량 18이 필요하다면? 답은 19. (H=19로 자르면 (22-19)+(30-19)+(25-19) = 20 ≥ 18, H=20이면 17이라 부족)
이 문제, 어떻게 접근할까? (핵심 아이디어)
처음엔 막막합니다. "어느 케이크를 얼마나 자를까?"를 직접 정하려 하면 경우의 수가 너무 많으니까요.
발상의 전환 — 자를 위치를 고르지 말고, 답(칼날 높이 H)을 먼저 가정해봅니다.
- •"칼날 높이가 H일 때 모이는 양이 필요량 이상일까?" → 이건 모든 케이크를 한 번 훑어
Σ max(0, 높이 - H)로 빠르게 검사됩니다. - •H가 낮으면 많이 잘려 양이 많고(가능), H가 높으면 적게 잘려 양이 적습니다(불가능). 즉 H에 대해 단조적이에요.
- •단조적이라면? 이분탐색으로 "양을 채우는 최대 H"를 찾을 수 있습니다.
이게 바로 매개변수 탐색(Parametric Search) — *정답 자체를 이분탐색하는* 기법입니다. 정렬된 배열에서 값을 찾는 게 아니라, 답의 후보 범위(0 ~ 가장 높은 케이크) 를 좁혀가는 거죠.
왜 헷갈릴까?
대부분 "이분탐색 = 정렬된 배열에서 값 찾기"로만 배웁니다. 그래서 *"답을 이분탐색한다"* 는 발상이 처음엔 잘 안 떠오릅니다.
그런데 한 번 눈으로 보면 완전히 다르게 와닿습니다.
1. 후보 높이 H를 하나 정한다 (범위의 가운데 = mid)
2. 그 H로 칼날을 그어, 위로 잘리는 양을 모두 더한다
3. 충분하면 H를 키우고(더 높은 칼날 도전), 부족하면 줄인다
4. 범위가 좁혀지며 정답에 수렴한다
이 흐름을 단계별 애니메이션으로 따라가면 "아, *이래서* 이분탐색이구나"가 한 번에 이해됩니다.
직접 눈으로 확인하기
케이크들이 막대로 세워지고, 빨간 칼날 선(H)이 위아래로 움직이며, 잘리는 윗부분이 한눈에 표시되는 전 과정을 단계별 시각화로 준비했습니다. 변수의 변화(lo·mid·hi, 모인 양)까지 같이 보입니다.
매개변수 탐색은 "나무 자르기", "공유기 설치", "예산 배분" 등 수많은 변형으로 코딩테스트에 등장합니다. 한 번 원리를 눈으로 익혀두면 어떤 옷을 입고 나와도 풀 수 있습니다.