파라메트릭서치 (Parametric Search)

파라메트릭 서치

생각보다 받아들이는데 어려운 개념이다.

이 알고리즘은 최적화 문제를 결정 문제로 바꾸는 기법이다.

조건을 만족하면서도 최대한 많이 가져갈 수 있는 방법을 찾는 느낌?? 혹은

조건을 만족하면서도 최대한 적게 가져갈 수 있는 방법을 찾는 느낌이라고 생각하면 좋다.

 

예시를 들어보면 아래의 문제를 인용해서 생각해보자.

BOJ2110 공유기 설치

대표적인 파라메트릭 서치 문제다.

공유기 C개를 설치해야 하는데 두 공유기 사이의 거리를 최대한으로 하려면 어느 정도쯤에 설치해야 할까?라는 문제다.

 

(아래의 예시는 위의 문제 스포가 될 수 있어서 임의로 그냥 생각한 풀이입니다.)

예를 들어보자.

공유기 3개를 설치해야 하는데

만약에 내가 두 공유기 사이의 거리를 2로 설치한다고 가정했을 때,

2씩 공유기를 설치해보니 공유기 3개가 모두 설치되었다. 이는 조건을 만족하니까 우리가 찾는 정답이므로 2로 갱신한다.

 

그렇다면, 여기서 끝일까? 아니다.

한 발자국 더 나아가 보면서 생각해 봐야 한다.

두 공유기 사이의 거리를 3으로 확장해보면 어떨까?

3씩 공유기를 설치해보니 공유기 3개가 모두 설치되었다. 분명 2일 때도 공유기 3개가 모두 설치되었는데? 조금 더 멀리 설치해도 공유기 3개가 모두 설치된 것이다. 마찬가지로 조건을 만족하니까 기존에 저장했던 2를 3으로 갱신한다.

 

그렇다면, 진짜로 끝일까? 아니다.

한 발자국 더 나아가 보자.

두 공유기 사이의 거리를 4로 확장해보면?

4씩 공유기를 설치해보니 공유기 2개가 설치되고 1개는 설치되지 못했다.

이렇게 된다면 주어진 조건 공유기 3개를 설치하지 못했으므로 정답이 아니다.

따라서 여기서 탐색을 멈춘다. 즉, 정답에 저장된 3이 답이 된다.

 

이렇듯, 범위를 좁혀가면서 주어진 조건을 만족하면 한 걸음 더 나아가 보고 아니라면 돌아오는 느낌으로 탐색을 하면 된다.

 

이런 기법은 많은 문제를 풀면 느낌이 오게 된다.

아래의 문제들은 백준 사이트에서 파라메트릭 서치 대표 문제들이다.

시간 나면 다시 풀어보자.

랜선 자르기

기타 레슨

공유기 설치

나무 자르기

 

기본적인 구현은 다음과 같이 생각하면 좋다.

1. 초깃값 세팅 start, end

2. mid가 결정된 후 그 mid가 조건에 맞는지 검사하기

3. 조건에 따라 범위 수정 후에 다시 2번으로 돌아가기

int start = 0; // 문제마다 start와 end 값은 변동될 수 있다.
int end = 1e8; // 범위가 커진다면 long long 자료형으로 오버플로우를 방지할 수 있다.
int ans = 0;
while(start <= end)
{
    int mid = (start + end) / 2;
    if(calc(mid)) // 조건을 만족한다면
    {
    	ans = mid;
        s = mid + 1; // 한 걸음 더 가보자.
    }
    else
    	e = mid - 1; // 조건을 만족하지 못하니까, 탐색 범위를 줄여보자.
}

또, 파라메트릭 서치 같은 문제들은 범위가 어마어마하게 크다. 보통 O(N)으로 해결될 수 없는 문제들 같은 경우 이러한 방법도 생각해보는 것도 좋다.