알고리즘 코딩 테스트에서 "조건을 만족하는 가장 큰 값을 구하시오" 혹은 "조건을 만족하는 가장 작은 값을 구하시오"라는 최적화(Optimization) 문제를 자주 마주하게 됩니다. 이때 답이 될 수 있는 값의 범위가 1부터 10억까지라면, 모든 경우의 수를 하나씩 대입해보는 브루트 포스(Brute Force) 방식은 가차 없이 시간 초과(TLE)를 발생시킵니다. 이럴 때 문제의 관점을 완전히 뒤집어, 거대한 최적화 문제를 "이 값이 정답이 될 수 있는가? (Yes or No)"라는 단순한 스무고개 질문(결정 문제, Decision Problem)으로 변환하여 O(log N)의 압도적인 속도로 정답을 핀포인트로 찾아내는 마법 같은 기법이 있습니다. 바로 파라메트릭 서치(Parametric Search)입니다. 이진 탐색(Binary Search)의 꽃이자 심화 응용인 파라메트릭 서치의 동작 원리와 절대적인 성립 조건을 완벽하게 해부해 보겠습니다.
1. 최적화 문제를 결정 문제로 뒤집기
파라메트릭 서치의 핵심은 질문의 형태를 바꾸는 것입니다. 예를 들어 "랜선 N개를 잘라서 만들 수 있는 랜선의 최대 길이는 얼마인가?"라는 최적화 문제가 있다고 가정해 보겠습니다.
- 최적화 관점: 최대 길이를 구하기 위해 1cm부터 시작해 점점 늘려가며 계속 랜선을 잘라봅니다. (시간 초과 발생)
- 결정(Decision) 관점: "랜선의 길이를 X로 설정했을 때, 우리가 원하는 개수 N개를 만들 수 있는가? (True / False)"로 질문을 바꿉니다.
만약 X = 100cm로 잘랐을 때 N개를 만들 수 있다면(True), 100cm보다 짧은 90cm, 80cm로 잘라도 무조건 N개를 만들 수 있음이 보장됩니다. 반대로 X = 200cm로 잘랐을 때 N개를 만들 수 없다면(False), 200cm보다 긴 210cm, 300cm로 잘라도 절대 N개를 만들 수 없습니다. 이처럼 특정 임계점을 기준으로 결과가 True의 연속에서 False의 연속으로(혹은 그 반대로) 완벽하게 뒤바뀌는 성질을 가지게 됩니다.
2. 파라메트릭 서치의 필수 전제 조건: 단조성(Monotonicity)
파라메트릭 서치를 코딩 테스트에 적용하려면 해당 문제가 반드시 단조 증가(Monotonically Increasing) 또는 단조 감소(Monotonically Decreasing) 성질을 띠어야만 합니다.
함수 isValid(X)를 만들었을 때, X가 커짐에 따라 그 결괏값이 True, True, True, False, False, False 처럼 어느 한순간을 기점으로 완벽하게 두 동강으로 나뉘어야 합니다. 만약 True, False, True, False처럼 결과가 뒤죽박죽 섞여서 나온다면, 이진 탐색으로 절반씩 날려버리는 논리가 전혀 성립하지 않기 때문에 파라메트릭 서치를 절대 사용할 수 없습니다.
3. 3단계 구현 로직과 Upper Bound의 융합
파라메트릭 서치의 실제 코드는 이진 탐색과 99% 동일하지만, 타겟(Target)을 찾는 것이 아니라 '경계값(True와 False가 나뉘는 지점)'을 찾는다는 점이 다릅니다.
3-1. 탐색 범위 설정과 시뮬레이션
// 파라메트릭 서치 기본 뼈대 (Java 예시)
long low = 1; // 정답이 될 수 있는 가장 작은 값
long high = 1000000000; // 정답이 될 수 있는 가장 큰 값
long answer = 0;
while (low <= high) {
long mid = (low + high) / 2;
// isValid(mid) : mid 길이로 잘랐을 때 조건을 만족하는가?
if (isValid(mid)) {
// 만족한다면, 더 '긴' 길이도 가능한지 확인하기 위해 오른쪽 탐색
answer = mid; // 일단 현재까지의 최적의 정답으로 기록
low = mid + 1;
} else {
// 불가능하다면, 길이를 줄여야 하므로 왼쪽 탐색
high = mid - 1;
}
}
return answer;
위 코드에서 가장 중요한 부분은 isValid(mid)가 참(True)일 때, 즉시 종료(Return)하지 않고 answer 변수에 기록만 해둔 채 탐색 범위를 계속해서 오른쪽으로 좁혀 나간다(low = mid + 1)는 것입니다. 이는 "100cm가 된다고? 그럼 혹시 101cm도 되는지 가보자!"라며 끝을 볼 때까지, 즉 Upper Bound(상한선) 직전까지 집요하게 밀어붙여 최댓값을 찾아내는 파라메트릭 서치의 핵심 메커니즘입니다.
1. 파라메트릭 서치(Parametric Search)는 "최댓값/최솟값을 구하라"는 최적화 문제를 "X일 때 조건이 만족하는가?"라는 결정 문제로 바꾸어 이진 탐색을 돌리는 고급 기법입니다.
2. 정답 후보 공간이 단조 증가/감소 (True와 False가 명확히 분리되는 형태) 구조일 때만 사용할 수 있으며, 시간 복잡도는 O(log(범위) * isValid 연산시간)이 됩니다.
3. 조건을 만족하더라도 탐색을 바로 종료하지 않고, 변수에 최적값을 계속 덮어씌우며(갱신하며) low나 high 포인터를 끝까지 이동시켜 극한의 경계값을 찾아내는 것이 구현의 핵심입니다.