Parametric Search Algorithm( 백준 1654번 )

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

개인적으로, 매우 좋은 문제였다. 최적화 문제를 결정 문제로 변화하여 풀 수가 있다니...

1 | 이진 탐색(Binary Search)

 

 이진 탐색은 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘이라고 할 수 있습니다. 

이진 탐색은 처음에 중간값을 선택하여 그 값과 찾으려는 값을 비교하여 클 경우 선택했던 중간값을 최솟값으로, 작을 경우 중간값을 최댓값으로 하여 원하는 값을 찾을 때까지 이 과정을 반복하는 알고리즘입니다.

한 과정을 거칠 때마다 탐색하는 범위가 절반씩 줄어드므로 시간 복잡도는 O(log N)를 가지게 됩니다. 따라서 빠른 속도를 가진 탐색 알고리즘이며 대신 정렬된 값들이 아닐 경우 탐색을 할 수 없다는 단점을 가집니다.

 

이해를 돕기 위해 아래에 하나의 예시를 들도록 하겠습니다.( 예시는 편의상 반말로 진행하도록 하겠습니다..양해부탁드려요:) )

 

1

2

3

4

5

6

7

8

9

 

 

위와 같이 1부터 9까지 주어졌을 때 3라는 값을 찾는다 가정해보자.

이진 탐색의 흐름은 다음과 같다.

1. 중간값인 5가 3보다 큰지 작은지 검사한다.

2. 3 < 5 이므로 5부터 9까지는 배제하고 1부터 4까지 중에서 다시 중간값( (1+4)/2 = 2.5 -> 2)과 3을 비교한다.

3. 2 < 3 이므로 1부터 2까지는 배제하고 3부터 4까지 중에서 중간값( (3+4)/2 = 3.5 -> 3)과 3을 비교한다.

4. 일치하므로 탐색 종료.

 

아래는 C++ 로 구현한 이진 탐색 함수입니다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int binarySearch(int array[], int value, int low, int high) {      if(low > high) {          return false;      }      int mid = (low+high) / 2;      if(array[mid] > value) {          return binarySearch(array, value, low, mid-1);      }      else if(array[mid] < value) {          return binarySearch(array, value, mid+1, high);      }      else {          return mid;      } } Colored by Color Scripter

cs

 

 

2 | 파라메트릭 서치(Parametric Search)

 

그렇다면 파마메트릭 서치는 어떨까요?

파라메트릭 서치는 이진탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가

장 일치하는 값을 찾아내는 알고리즘입니다.

이진탐색이 1부터 9까지의 값에서 3이라는 값을 찾는 알고리즘이라면 파라메트릭 서치는 1부터 9까지의 범위 내에서 3이

라는 값(또는 원하는 조건에 부합하는 값)을 찾아가는 것이라는 차이가 있습니다. 따라서 주어진 값 중에서 탐색하는 이진

탐색과는 다르게 파라메트릭 서치는 주어진 것이 값이 아니라 범위이기 때문에 특정한 상활을 최적화시키는 문제를 풀 때

용이하다는 장점을 가집니다.

실제로 파라메트릭 서치를 사용하면 최적화 문제를 결정 문제로 바꾸어 풀 수 있게 되어 문제 접근이 상당히 용이해집니다. 

최적화 문제를 결정 문제로 바꾸어 푼다는 말은 주어진 상황에서 최솟값, 최댓값 등의 특정 값을 구하는 문제를 특정 값이

어떠한 조건을 만족하는지만 확인하면 되는 문제로 바뀐다는 의미입니다.

예를 들어봅시다.

배가 7시간마다 고파지는 사람이 하루를 배부르게 지내기 위한 최소한의 식사횟수는 몇회인지에 구하는 문제가 있다고 가

정해보자.(글에서 주어지는 예시에서는 소수점 첫째자리까지만 계산한다.)

잠자는 시간등을 고려하지 않는다고 계산할 때 24시간을 식사횟수로 나눴을 때 7 또는 7에 가장 가까운 값이 나오도록 하

는 것이 이 문제를 풀기 위한 조건이라고 할 수 있다.

0끼부터 10끼가지의 식사가 가능하다고 할 때

 

-첫 번째 단계

0                                                           5                                                              10

                                                                                                                  △(중간값)

범위가 0부터 10까지이므로 (0+10)/2 = 5를 중간값으로 하여 조건에 부합한지 검사해본다.

24 / 5 =4.8 이므로 원하는 값인 7보다 작다. 즉 나누는 값이 더 작아져야하므로 5 바로 밑에 있는 값인 4.9를 범위의 최댓값으로 하여 반복한다.

 

-두 번째 단계

 

0                                                         2.4                                                            4.9

 

24 / 2.4 = 10 이므로 원하는 값인 7보다 크다. 따라서 이번엔 중간값이였던 2.4 바로 윗값인 2.5를 최솟값으로 하여 2.4부터 4.9까지의 범위로 다시 반복합니다.

.

 

위의 과정을 반복하다보면 탐색범위와 중간값은 0-10(5) -> 0-4.9(2.4) -> 2.5-4.9(3.7) -> 2.4-3.6(3) -> 3.1-3.6(3.3) -> 3.4-3.6(3.5) -> 3.4-3.4(3.4) -> 3.4-3.3(3.3) 으로 변화할 것이며 범위의 시작값과 끝값의 대소관계가 역전되는 순간 탐색이 종료된다.

역전되기 직전 중간값인 3.4가 구하고자 하는 값이며 24를 7로 나눴을 때의 소수점 첫째짜리까지의 값이 3.4이므로 올바르

게 탐색이 되었다.

위 예시의 핵심은 배부르게 지내기 위해 하루 최소 몇 회의 식사를 먹어야 하는가? 에 대한 최적화 문제가 하루에 식사를 R

번 했을 때 배부르게 지낼 수 있는가에 대한 결정 문제로 바뀌었다는 것입니다. 문제의 조건이 복잡하거나 문제의 상황상

최적화시키기 위한 프로그래밍적 구현이 어려울 때는 이 파라메트릭 서치라는 알고리즘을 떠올리고 상황에 맞게 변형하여

이용해보시면 좋을 것 같습니다. 

 

아래는 이 문제에서의 파라메트릭 서치 구현입니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

float parametricSearch(float start, float end) {     float mid, tempMid;     while(start<=end) {         mid = tempMid;         tempMid = (start+end)/2.0;         if(24/tempMid > 7) {             start = tempMid+0.1;         }         else if(24/tempMid < 7) {             end = tempMid-0.1;         }         else {             break;         }     }     return mid; }