티스토리 뷰
파라메트릭 서치는 최적화 문제( 조건에 만족하는 최소 or 최대를 구하는 문제 ) 를 결정 문제로 바꿔 푸는 것이라 할 수 있다고 한다
여기서 결정 문제는 답이 yes or no로 도출되는 문제를 의미한다.
간단한 예를 들어보자.
먼저 나이 순으로 정렬된 사람들이 있다고 하자. 그리고 만 18세 이상의 사람들은 민증을 누구나 가지고 있다고 하자. 그럼 이 중에서 민증을 가진 사람 중 가장 어린 사람은 누구인지 구하는 문제를 어떻게 해결할 수 있을까?
가장 쉬운 방법은 앞에서 차례대로 민증을 가지고 있는지를 물어봐서 가장 먼저 민증을 가지고 있다고 대답한 사람을 찾는 것일 것이다.
그러나 파라메트릭 서치를 이용해 이 최적화 문제를 결정 문제로 바꾼다면, log 시간 안에 문제를 풀어낼 수 있다.
이 문제라면, 최적화 문제와 결정 문제는 각각 아래와 같다.
최적화 문제 : 민증을 가지고 있는 사람 중 가장 어린 사람 ( 이것은 배열의 최솟값이라고 할 수 있을 것이다. )
결정 문제 : 민증을 가지고 있는지를 물어본다 -> Yes or No로 나뉠 것이다.
이제 모든 사람들은 정답의 후보가 될 수 있기 때문에 L-R범위를 전체로 지정해 이분 탐색을 통해 탐색한다.
그리고 (L+R)/2 의 바닥값을 MID로 설정한다.
만약 MID 위치의 사람이 민증을 가지고 있지 않다면, 정답자는 현재 MID위치 사람보다 뒤에 있기 때문에 L을 MID + 1 로 옮겨 MID를 다시 설정한다.
만약 MID 위치의 사람이 민증을 가지고 있다면 R을 MID-1 위치로 옮겨 MID를 재설정한다.
이때 만약 L과 R이 같다면 MID 위치의 사람이 민증을 가지고 있을 때, 현재 MID위치의 사람이 민증을 가진 최연소자 즉 정답자가 되며,
그렇지 않다면 이전에 MID 위치 사람이 정답자가 된다.
이처럼 파라메트릭 서치는 문제를 풀어나가는 과정이 바이너리 서치( 이분탐색 )과 비슷하다.
파라메트릭 서치의 핵심은 결정 문제이다. 이 때, 결정 문제를 쉽게 풀수 있어야( 정답이 될 수 있는 값인지 아닌지를 쉽게 판단할 수 있어야 ) 최적화 문제를 파라메트릭 서치로 바꿔 풀기에 적합하다.
또한 정답이 될 수 있는 값들이 연속적이어야 파라메트릭 서치를 이용할 수 있다.
이때, 정답이 될 수 있는 값들이 연속적이어야 한다는 말은 정답이 X라고 했을 때, X이상의 값들은 모두 조건에 만족할 수 있어야 한다는 것이다.
즉,
1) 결정문제를 정의했을 때, 쉽게 풀 수 있는 경우
2) ( 최솟값을 구하는 경우 ) 최솟값이 X라면, X이상의 값에 대해서는 모두 조건을 만족
3) ( 최댓값을 구하는 경우 ) 최댓값이 X라면, X이하의 값에 대해서는 모두 조건을 만족
이 세가지 조건을 충족한다면, 파라메트릭 서치를 이용해 문제를 풀 수 있다.
[ 파라메트릭 서치와 이진탐색의 차이 ]
이진탐색은 mid 위치의 값이 찾고자하는 값과 정확히 일치하는 지를 찾는 탐색이다.
그러나 파라메트릭 서치는 이용자의 조건에 따라 다양한 구현과 결과가 나올 수 있다.
예를 들어, 정렬된 수 1, 3, 4, 6, 9, 10, 11, 13, 15, 19에서 14보다 작은 수의 갯수를 구해보도록 하자.
이를 위해서는 mid 위치의 좌측과 우측을 동시에 확인하며 탐색하는 방법을 이용하면 쉽게 찾아낼 수 있다.
이렇 듯 비슷한 문제풀이 과정을 가지고 있지만 필요에 맞게 변형하여 푼다는 점에서 이진탐색과 다르다는 것을 알 수 있다.
( 참고로 이진 탐색도 해당 값과 같고 다름 두가지 결과를 이용해 해당 값을 찾는 일종의 결정 문제라고 할 수 있을 것 이다. )
[ by 공대여자's 님의 블로그
http://sarah950716.tistory.com/16, http://sarah950716.tistory.com/20 ]