파라메트릭 서치란 최적화 문제를 결정 문제로 바꿔 이분 탐색을 이용해 해결하는 방법이다. 여기서 결정 문제란 예 혹은 아니오 형태의 답이 나오는 문제를 말한다. 예를 들어 외판원 문제를 최적화 문제와 결정 문제로 표현하면 아래와 같다.
- optimize(G) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환한다.
- decision(G, \(x\)) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 길이가 \(x\)이상인 경로가 있는 있는가?
최적화 문제의 답은 보통 실수, 정수이므로 답의 경우의 수가 무한개이지만, 결정 문제의 답은 예 혹은 아니오 이므로 답의 경우의 수가 2개이다.
왜 결정문제로 바꿔서 푸는가?
최적화 문제를 결정 문제로 바꾼 후 결정 문제를 해결하여 최적화 문제를 해결하는 방법이 이득이 되는 경우는 아래와 같을 것이다.
- 최적화 문제를 푸는 것이 더 어렵다.
- 둘 다 정말 어렵다
그렇다면 최적화 문제를 해결하여 결정 문제를 해결하는 경우는 어떨까? 최적화 문제의 해답을 알고 있다면 결정 문제를 해결하는 것은 매우 쉽다. 왜냐하면 단순히 최적화 문제의 답과 비교하여 참, 거짓을 얻으면 되기 때문이다.
// 최적화 문제의 답을 반환하는 함수
double optimize();
// 결정 문제의 답을 반환하는 함수
bool decision(number) {
return optimize() <= number;
}결정 문제는 최적화 문제보다 어려울 수 없으니 어떤 최적화 문제를 결정 문제로 바꿀 수 있다면, 결정 문제를 통해 최적화 문제를 해결하는 것이 이득이 될 것이다.
파라메트릭 서치로 풀리는 문제
최적화 문제를 결정 문제로 바꾼 뒤 이분 탐색을 이용해 해결하기 때문에 결정 문제의 답 구간의 참 또는 거짓이 한 번 변해야 한다.
예를들어 어떤 외판원 문제의 답이 5라고 할 때 결정 문제를 다음과 같이 정의하자.
decision(G, \(x\)) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 길이가 \(x\)이상인 경로가 있는 있는가?
그렇다면 답의 참 거짓 분포는 아래 사진과 같을 것이다.
파라메트릭 서치의 답
우리가 찾는 것은 결정 문제의 참을 만족하는 최솟값, 최댓값이다. 이 값을 이분 탐색으로 구하면 되는데 이분 탐색의 while문 종료 조건은 사람마다 다르며 각자 기준을 정하는 것이 헷갈리지 않는다. 앞으로 반복문 종료 조건은 lh > rh이다.
결정 문제를 만족하는 최솟값 구하기
답 구간이 False → True 일 때 결정 문제의 참, 거짓을 결정하는 함수 decision(x)를 만족하는 \(x\)의 최솟값을 찾아보자.
결정 함수를 세웠다면 decision(mid)가 참일 경우 mid = rh - 1로, 거짓일 경우 mid = lh + 1로 바꿔 lh와 rh를 이동시키면서 이분 탐색을 진행한다.
이때, decision(mid)의 값이 거짓에서 참으로 바뀌는 지점에서 lh와 rh가 교차가 일어나 반복문이 종료된다. 이때 결정 함수를 만족하는 \(x\)의 최솟값은 lh이 된다.
결정 문제를 만족하는 최댓값 구하기
답 구간이 반대로 True → False 일 때 결정 문제의 참 거짓을 결정하는 함수 decision(x)를 만족하는 \(x\)의 최댓값은 rh이다.
파라메트릭 서치의 주요 아이디어
파라메트릭 서치는 보통 최적화 문제에서 특정 값을 최대화하거나 최소화하는 최적 해를 구할 때 사용된다. 이때, 이진 탐색을 통해 문제를 해결하는 것이 핵심이다. 파라메트릭 서치의 과정을 요약하면 아래와 같다.
- 결정 문제로 변환: 주어진 최적화 문제를 “특정 값이 가능한가?“라는 결정 문제(Yes/No)로 변환한다.
- 이진 탐색 적용: 변환된 결정 문제에 대해 이진 탐색을 수행하여 최적값을 찾는다. 예를 들어, 최대값을 찾는 문제라면 가능한 값의 범위에서 이진 탐색을 하며, “이 값이 가능한가?“를 반복적으로 확인한다.
- 결정 함수 구현: 이진 탐색의 중간 값에 대해 결정 문제의 답을 구하는 함수(결정 함수)를 구현한다. 이 함수가 참이면 더 큰 값을 탐색하고, 거짓이면 더 작은 값을 탐색한다.
파라메트릭 서치의 적용 예시
[G2] 레이스
최적화 문제 : 심판 \(m\)명을 \(k\)개의 자리에 배치할 때 가장 가까운 두 심판의 거리의 최댓값을 구해라.
결정 문제 : 두 심판 사이의 최소 거리를 \(d\)라고 할 때 \(k\)개의 자리에 심판을 \(m\)명 놓을 수 있는가?
[G3] 제자리 멀리뛰기
최적화 문제 : \(m\)개의 작은 섬을 제거하여 탈출구에 도착할 때 학생들이 점프한 최소거리의 최댓값을 구하여라.
결정 문제 : 학생들이 최소 \(dist\)만큼 점프하면서 \(m\)개의 작은 섬을 제거해 탈출구에 도착할 수 있는가?
[G4] 성싶당 밀키트
최적화 문제 : 중요하지 않은 재료를 최대 \(k\)개까지 뺐을 때, 밀 키트를 구매 후 며칠 후까지 먹을 수 있는지 출력한다.
결정 문제 : 중요하지 않은 재료를 최대 \(k\)개 뺐을 때, 구매 후 \(x\)일에 먹을 수 있는가?
[G4] 휴게소 세우기
최적화 문제 : \(m\)개의 휴게소를 짓고 난 후에 휴게소가 없는 가장 긴 구간의 최솟값을 구해라.
결정 문제 : 가장 긴 휴게소 구간의 길이를 \(x\)라고 할 때 지어야 하는 휴게소 개수가 \(m\)개 이하인가?
[S2] 용돈 관리
최적화 문제 : 용돈을 정확히 M번만 인출하기 위한 통장에서 인출해야 할 최소 금액을 구해라.
결정 문제 : 용돈을 \(x\)만큼 인출할 때 인출해야 하는 횟수가 M번 이하인가?
[S3] 예산
최적화 문제 : 여러 지방의 예산 요청과 국가 예산 총액이 주어졌을 때 문제의 조건을 만족하는 예산 상한액의 최대값을 구해라.
결정 문제 : 여러 지방의 예산 요청과 국가 예산 총액이 주어졌을 때 예산 상한액 \(x\)을 가지고 예산을 배정할 수 있는가?
[LeetCode Medium] Maximum Tastiness of Candy Basket
최적화 문제 : 서로 다른 \(k\)개의 사탕을 고를 때, 캔디 바구니의 맛(캔디 가격들 간의 최소 절대 차이)의 최대 값을 구해라.
결정 문제 : 캔디 바구니의 맛이 최소 \(x\) 이상일 때 \(k\)개의 서로 다른 캔디를 선택할 수 있는가?