고속도로에 충전소를 어디에 둘까?
전기차가 늘면서 고속도로 휴게소마다 충전 줄이 길어집니다. 일직선 위에 휴게소가 여러 곳 있고, 예산 때문에 딱 C곳에만 충전소를 설치할 수 있다면 — 어디에 둬야 할까요?
핵심은 이겁니다. 충전소가 한곳에 몰리면 멀리 떨어진 구간은 충전이 불편합니다. 그래서 "가장 가까운 두 충전소 사이의 거리"를 최대한 멀게 만드는 게 목표예요.
예: 휴게소가 3, 6, 12, 17, 25, 30(km)에 있고 충전소 3개를 둔다면? 답은 13km. (3·17·30에 두면 간격이 14, 13 → 최소 13)
이 문제, 어떻게 접근할까? (핵심 아이디어)
처음엔 막막합니다. "어느 휴게소를 고를까?"를 직접 정하려 하면 조합의 수가 폭발하니까요.
발상의 전환 — 위치를 고르지 말고, 답(최소 거리 D)을 먼저 가정해봅니다.
- •"충전소 사이 최소 거리가 D 이상이 되게 C개를 놓을 수 있을까?" → 이건 그리디로 빠르게 검사됩니다. (맨 앞 휴게소에 무조건 설치하고, 직전 설치점에서 D 이상 떨어진 곳마다 설치)
- •D가 작으면 놓기 쉽고(가능), D가 크면 어렵습니다(불가능). 즉 D에 대해 단조적이에요.
- •단조적이라면? 이분탐색으로 "가능한 최대 D"를 찾을 수 있습니다.
이게 바로 매개변수 탐색(Parametric Search) — *정답 자체를 이분탐색하는* 기법입니다. 정렬된 배열에서 값을 찾는 게 아니라, 답의 후보 범위를 좁혀가는 거죠.
왜 헷갈릴까?
대부분 "이분탐색 = 정렬된 배열에서 값 찾기"로만 배웁니다. 그래서 *"답을 이분탐색한다"* 는 발상이 처음엔 잘 안 떠오릅니다.
그런데 한 번 눈으로 보면 완전히 다르게 와닿습니다.
1. 후보 거리 D를 하나 정한다
2. 그 D로 충전소를 맨 앞부터 하나씩 놓아본다 (그리디)
3. 놓은 개수가 충분하면 D를 키우고, 부족하면 줄인다
4. 범위가 좁혀지며 정답에 수렴한다
이 흐름을 단계별 애니메이션으로 따라가면 "아, *이래서* 이분탐색이구나"가 한 번에 이해됩니다.
직접 눈으로 확인하기
휴게소가 수직선 위에 놓이고, 후보 거리 D가 좁혀지고, 충전소가 그리디로 하나씩 놓이는 전 과정을 단계별 시각화로 준비했습니다. 변수의 변화(lo·mid·hi, 설치 개수)까지 한눈에 보입니다.
매개변수 탐색은 "공유기 설치", "나무 자르기", "예산 배분" 등 수많은 변형으로 코딩테스트에 등장합니다. 한 번 원리를 눈으로 익혀두면 어떤 옷을 입고 나와도 풀 수 있습니다.