파라메트릭 서치는 이분 탐색을 배운 뒤 한 번 더 넘어야 하는 벽처럼 느껴지는 주제입니다. 정렬된 배열에서 값을 찾는 이분 탐색은 이해했는데, 어떤 문제는 배열도 없고 정답도 직접 보이지 않는데 갑자기 이분 탐색을 써야 하니 감이 끊기는 것입니다.
이번 글에서는 파라메트릭 서치를 어려운 용어로 설명하지 않고, 조건을 만족하는 답의 경계를 찾는 이분 탐색으로 설명하겠습니다.
보통 이분 탐색과 무엇이 다를까
일반적인 이분 탐색은 정렬된 배열에서 특정 값을 찾는 그림이 먼저 떠오릅니다. 예를 들어 target이 있는지, 그 위치가 어디인지를 찾는 식입니다.
하지만 파라메트릭 서치는 값 하나를 직접 찾기보다, 어떤 답이 가능한지 아닌지를 판별하는 함수를 먼저 만듭니다. 그리고 그 함수가 어느 지점부터 true/false로 갈리는지 경계를 찾습니다.
즉 문제의 초점이 “이 숫자가 맞는가?”가 아니라 “이 숫자를 답으로 잡아도 조건을 만족하는가?”로 이동합니다.
왜 이분 탐색이 답 찾기로 확장될 수 있을까
핵심은 단조성입니다. 어떤 값 x가 가능하면 그보다 작은 값들도 다 가능하거나, 반대로 어떤 값 x가 가능하면 그보다 큰 값들도 다 가능해야 합니다. 이렇게 가능/불가능이 한 방향으로 갈라지면 경계를 이분 탐색으로 찾을 수 있습니다.
예를 들어 “이 속도로 작업을 끝낼 수 있는가?”를 묻는 문제가 있다고 해보겠습니다. 속도를 높일수록 가능성이 커지는 구조라면, 불가능 구간과 가능 구간이 한 번만 갈립니다. 이때 경계를 찾는 것이 파라메트릭 서치입니다.
feasible 함수란 무엇일까
파라메트릭 서치의 실전 핵심은 배열이 아니라 feasible 함수입니다. 즉 특정 답 후보 mid를 넣었을 때, 이 값으로 조건을 만족할 수 있는지 true/false로 판단하는 함수를 만드는 것입니다.
def feasible(mid):
# mid를 답 후보로 잡았을 때 조건을 만족하는지 검사
return True or False
lo, hi = 1, 10**9
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
answer = lo입문자가 제일 자주 막히는 부분이 바로 이 feasible 함수입니다. 많은 사람이 mid를 정답처럼 다루려 하지만, 사실 mid는 정답 후보일 뿐입니다. 중요한 것은 “이 후보가 가능하냐”를 빠르게 검사하는 로직을 만들 수 있느냐입니다.
이 코드에서 중요한 것은 mid 자체가 아니라 feasible(mid)의 의미입니다. 즉 파라메트릭 서치는 이분 탐색 껍데기보다 판별 함수 설계가 본체라고 보는 편이 맞습니다.
최소 가능한 답과 최대 가능한 답은 어떻게 다를까
이 차이를 정확히 못 잡으면 코드가 항상 한 칸씩 밀리거나, 무한 루프에 빠지거나, 최솟값 대신 최댓값을 내는 오류가 생깁니다. 그래서 파라메트릭 서치는 이분 탐색 템플릿을 외우는 것보다, 지금 내가 찾는 경계가 어떤 종류인지 먼저 구분하는 습관이 더 중요합니다.
어떤 문제는 조건을 만족하는 최소 값을 구하고, 어떤 문제는 조건을 만족하는 최대 값을 구합니다. 그래서 경계를 어느 쪽으로 좁혀 가는지가 달라집니다.
최소 가능한 답을 구할 때는 feasible이면 더 왼쪽에도 답이 있는지 확인해야 하고, 최대 가능한 답을 구할 때는 feasible이면 더 오른쪽으로 갈 수 있는지 봐야 합니다. 이 차이를 못 잡으면 코드 모양은 맞아도 답이 한 칸씩 밀리는 오류가 자주 납니다.
이 경계 감각은 lower bound와 upper bound 글과도 직접 연결됩니다.
문제에서 어떤 신호가 보이면 파라메트릭 서치일까
- 정답이 크기, 길이, 용량, 속도 같은 숫자 범위로 주어진다
- 어떤 값이 가능/불가능인지 판별하는 방식으로 바꿀 수 있다
- 가능한 값 구간과 불가능한 값 구간이 한 방향으로 갈린다
- 정답을 직접 찾기보다 조건을 만족하는 최솟값이나 최댓값을 묻는다
이 신호가 보이면 배열이 없어도 이분 탐색을 떠올릴 수 있어야 합니다. 바로 그 지점이 일반 이분 탐색과 파라메트릭 서치의 연결 지점입니다.
예를 들어 최소 가능한 답을 찾는 문제에서 feasible(mid)가 true면, 정답이 더 왼쪽에도 있을 수 있으므로 hi를 줄입니다. 반대로 최대 가능한 답을 찾는 문제에서는 true일 때 lo를 키워야 합니다. 이 방향을 헷갈리면 파라메트릭 서치는 항상 “거의 맞는 오답”이 됩니다.
자주 하는 실수
- feasible 함수를 못 만들고 정답을 직접 시뮬레이션하려 한다
- 단조성이 없는 문제를 억지로 이분 탐색에 끼워 맞춘다
- 최소 답을 구하는지 최대 답을 구하는지 헷갈린다
- 탐색 범위(lo, hi)를 너무 대충 잡아서 예외가 생긴다
특히 단조성이 없으면 파라메트릭 서치는 성립하지 않습니다. 즉 이분 탐색 코드를 외우는 것보다, feasible 함수가 한 방향으로만 바뀌는지를 먼저 보는 습관이 중요합니다.
결국 파라메트릭 서치는 숫자를 찍는 알고리즘이 아니라 경계를 읽는 알고리즘입니다. 이 경계 그림이 머릿속에 들어오면, 배열이 없어도 “아 이건 이분 탐색으로 답을 찾는 문제구나” 하고 보이기 시작합니다.
마무리
파라메트릭 서치를 이해하는 핵심은 이분 탐색을 배열 속 숫자 찾기에서 꺼내어, 조건의 경계를 찾는 도구로 다시 보는 데 있습니다.
즉 정답을 직접 찾지 말고, 정답 후보가 가능한지 판별하는 문제로 바꾼다는 사고 전환이 가장 중요합니다.
