파라메트릭 서치 (Parametric Search)
쉽게 풀면
"나무를 잘라 필요한 길이의 목재를 최대한 많이 얻으려면 절단 높이를 얼마로 정해야 할까?" 같은 최적화 문제를 떠올려 봅시다. 가능한 절단 높이를 하나하나 다 시도해 보면 시간이 너무 오래 걸립니다. 파라메트릭 서치는 이런 "최적의 값은 얼마인가?"라는 질문을, "높이 h로 잘랐을 때 조건을 만족하는가(Yes/No)?"라는 훨씬 쉬운 판별 문제로 바꿔치기합니다. 그리고 이 Yes/No 판별을 이진 탐색으로 반복하면서 범위를 절반씩 좁혀 나가면, 결국 조건을 만족하는 경계값(최적값)을 빠르게 찾아낼 수 있습니다. 즉 "정답을 직접 구하기"가 아니라 "정답이 맞는지 확인하기"를 반복해서 정답에 접근하는 방식입니다.
왜 중요한가
파라메트릭 서치는 "최적값을 직접 계산하기 어렵지만 특정 값이 조건을 만족하는지는 쉽게 판별할 수 있는" 문제 유형에 폭넓게 적용할 수 있어, 알고리즘 설계와 최적화 연구에서 자주 활용되는 문제 해결 패러다임입니다. 자원 배분, 스케줄링, 네트워크 최적화처럼 "최댓값을 최소화" 또는 "최솟값을 최대화"하는 형태의 문제를 효율적으로 풀어야 하는 다양한 응용 분야의 알고리즘 설계에서 기본적인 도구로 다뤄집니다.
논문에서는 이렇게 쓰입니다
이 문장은 "일일이 값을 대입해 확인하는 대신, 이진 탐색으로 범위를 좁혀가며 조건을 만족하는 가장 작은 값을 훨씬 빠르게 찾아냈다"는 뜻입니다.
여러 노드에 자원을 어떻게 나눠줘야 가장 느린 노드의 지연 시간이 최소가 되는지를, 직접 계산하는 대신 후보 값이 조건을 만족하는지 반복 판별하는 방식으로 찾아냈다는 뜻입니다.
여러 작업을 기계에 배정할 때 전체 완료 시간을 최소화하는 값을 찾기 위해, 특정 시간 안에 모든 작업을 끝낼 수 있는지를 빠르게 판별하는 보조 알고리즘과 결합해 탐색했다는 뜻입니다.
조금 더 깊게 보면
파라메트릭 서치의 핵심은 원래의 최적화 문제를 "이 값 x로 가능한가?"라는 결정 문제(decision problem)로 변환하는 데 있으며, 이 판별 함수를 얼마나 빠르게 계산할 수 있는지가 전체 알고리즘의 효율성을 좌우합니다. 판별 함수 자체가 그리디 알고리즘이나 그래프 탐색처럼 별도의 알고리즘으로 구현되는 경우가 많아, 파라메트릭 서치는 흔히 다른 알고리즘 기법과 결합되어 사용됩니다. 값이 연속적인 실수 범위일 때는 특정 정밀도까지만 근사하여 반복 횟수를 제한하는 방식이 실무에서 흔히 쓰입니다.
주의할 점
파라메트릭 서치가 성립하려면 판별 함수(어떤 값 이상 또는 이하에서는 항상 조건을 만족하고, 그 반대편에서는 항상 만족하지 않는 성질, 즉 단조성)가 반드시 보장되어야 합니다. 이 단조성이 깨지면 탐색 알고리즘 자체가 정답을 놓칠 수 있으므로, 파라메트릭 서치를 적용하기 전에 판별 조건이 단조로운지부터 확인해야 합니다.