Parametric Search
문제를 결정 문제로 변형하여 이분탐색으로 해결하는 방식입니다.
개념
처음들으면 잘 와닿지 않을 수 있다. 예시를 통해서 살펴봅시다.
예를들어 손님이 고기 200g을 달라고 해서 고기 덩이에서 200g을 잘라내야한다고 해봅시다.우리는 보통 눈대중으로 잘라서 저울에 재본 후 200g보다 부족하면 조금 더 잘라넣고 200g을 넘어가면 덩어리를 잘라서 저울에 잰다.
즉 우리는 "고기 200g을 잘라라"라는 문제를 "지금 자른 고기가 200g보다 무거운가"라는 결정문제로 변형한 뒤 조금씩 고기를 추가하거나 덜어내면서((=이분탐색)으로 문제를 해결한다. 이렇게 원래 주어진 문제를 결정문제로 변형하여 이분탐색을 통해 해결하는 것을 파라메트릭 서치라고 한다.
사용 조건
아래 세 조건을 만족하는 문제에서만 사용할 수 있습니다.
1.특정 조건을 만족하는 최대/최소를 구하는 형식의 문제여야 합니다.
조건이 보이지 않더라도 최소한 해당 조건으로 문제를 변경할 수 있어야합니다. 수행할 변수를 가지고 함수를 세웠을 때 그 함수가 감소함수거나 증가함수이어야 합니다.
2.어떤 값이 조건을 만족하면 이후 탐색 범위 내의 모든 값은 모두 조건을 만족해야한다.
최대값을 구하는 문제의 경우 어떤 값이 조건을 만족하면 그 값보다 작은 값은 모두 조건을 만족해야한다. 또한 최솟값을 구하는 경우 어떤 값이 조건을 만족하면 그 값보다 큰 값은 모두 조건을 만족해야합니다. 그래야 조건을 만족하는 경우, 만족하지 않는 경우 다음 범위를 탐색하면서 답을 구할 수 있습니다.
3.범위가 이산적이거나 허용오차 범위가 있어야합니다.
이분탐색으로는 연속적인 범위에서는 정답에 한없이 가까워질 뿐 정확한 값은 구할 수 없습니다. (=고등수학에서의 극한을 떠올리면 됩니다.)
구현
문제
condition(x)를 만족하는 최대값을 찾는 문제라고 가정합니다.
code
목표 : 후보 범위의 최솟값인 l과 h를 넉넉하게 잡아준 뒤 이를 점점 줄여나가면서 l과 h가 같아지도록 합니다.
whlie(l<h){
int m = (l+h+1)/2;
if(condition(m)){
l = m;
}else{
h = m-1;
}
}
주의 : 무한 루프에 빠지지 않는지 확인하기
m=(l+h)/2인지, m=(l+h+1)/2인지에 따라 무한루프에 걸릴 수 있습니다.
무한 루프에 빠지지 않게하려면 이분탐색에 의해 두 구역으로 나눠졌을 때 m이 어디에 속하는지를 확인하면 됩니다. 예를 들어 조건을 만족하는 최댓값을 구하는 경우 m은 h쪽 범위에 속합니다. l과 h가 1차이로 붙어 있을 때 그림은 다음과 같습니다.
m=(l+r)/2일 경우, 그림처럼 m은 항상 왼쪽 범위로 고정되고 오른쪽 범위는 변하지 않아서 무한 루프에 빠집니다.
m=(l+r+1)/2일 경우 m은 오른쪽 범위속하게 되면서 다음 범위는 [m,m]이 됩니다.
표로 정리해보겠습니다.
| 목표 | m의 값 |
|---|---|
| 조건 만족 최솟값 | m=(l+h)/2 |
| 조건 만족 최댓값 | m=(l+h+1)/2 |
시간 복잡도
- 범위가 m이면 루프는 logM번 실행됩니다.
- 조건 함수의 시간 복잡도 = O(C(n))
- 위 조건을 모두 고려하면 총 시간 복잡도는 O(C(n)logM)이 됩니다.
예제
최소 통과 시간
https://www.codetree.ai/missions/8/problems/minimum-transit-time?&utm_source=clipboard&utm_medium=text
parametirc search에서 결정 문제라는 표현을 썼었습니다. 그게 이 문제에서 어떻게 적용되는지 살펴보겠습니다. 이걸 결정 문제로 바꾸면 우리가 구해야하는 답을 인자로, 조건의 참 거짓을 판단하는 문제로 만들 수 있습니다.
1. 변수를 지정합니다. (보통은 문제에서 요구하는 최대값/최솟값입니다.)
2. 해당 변수를 이진탐색하면서 codition에 만는지 판단합니다.
3. condition을 정의합니다.
4. 기본 템플릿에 맞춰서 구현합니다.
기본 템플릿을 다시 봐봅시다.
whlie(l<h){
int m = (l+h+1)/2;
if(condition(m)){
l = m;
}else{
h = m-1;
}
}
위 템플릿을 적용하여 코드를 구현하면 다음과 같이 변형할 수 있습니다.
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokens;
static final long MAX_TIME = Long.MAX_VALUE;
public static void main(String[] args)throws IOException{
tokens = new StringTokenizer(buffer.readLine());
int n = Integer.parseInt(tokens.nextToken());
int m = Integer.parseInt(tokens.nextToken());
long[] passTimes = new long[m];
for(int i=0; i<m; i++){
passTimes[i] = Long.parseLong(buffer.readLine());
}
long l =1;
long h = MAX_TIME;
while(h>l){
long mid = (h+l)/2;
if(isValid(mid, passTimes, n)){
h = mid;
}else{
l = mid+1;
}
}
System.out.println(l);
}
private static boolean isValid(long target, long[] passTimes, int n){
long passCount = 0;
for(long time : passTimes){
passCount+= (target/time);
}
return passCount>=n;
}
}