[Algorithm] Parametric Search

파라메트릭 탐색(Parametric Search)

 

파라메트릭 탐색이란, 이분 탐색(Binary Search)과 비슷한 부류의 탐색이다.

이분 탐색의 경우 어떤 정답을 찾기 위해 탐색을 수행한다. 만약 원하는 정답이 나오지 않는 다면 검색 결과는 없음으로 나오게 된다.

해당 이분 탐색의 예제는 아래와 같다.

 

Address	0	1	2	3	4	5	6	7
Value	1	4	7	24	32	33	42	52

 

정렬(Sort)되어 있는 상태인 배열에서 우리는 7이라는 값을 찾고 싶다 라고 가정하자.

해당 배열에서의 left주소는 0, right주소는 7이 된다.

해당 값의 mid = (left+right)/2 = 7/2 = 3 이 된다.

그럼 최초에 Martrix[mid]의 값과 우리가 찾고자하는 7과 비교한다. 해당 값이 7보다 크다면 우리는 right값을 mid-1로 바꿀 것이며, 작다면 left값을 mid+1로 바꿀 것이다. 해당 방법을 반복해서 검색하다보면 우리는 O(logN)이라는 시간복잡도로 원하는 7이라는 값을 찾아낼 수 있다.

 

위에서 설명했듯이 이분 탐색은 어떤 정답을 찾기 위해 탐색을 수행한다.

하지만 아래에서 설명할 파라메트릭 탐색의 경우는 위의 경우와는 다르게 어떠한 값을 정답으로 가정하고, 이것이 맞는지 계속해서 검증해나가면서 정답을 찾아나가는 탐색이라 보면 된다.

 

추가적인 참조는 아래의 주소를 통해 공부하길 바란다.

http://sarah950716.tistory.com/16

http://hongjun7.tistory.com/133