이분탐색1 [파라메트릭 서치] Parametric Search의 이해 및 구현 "파라메트릭 서치" 최적화 문제를 결정 문제로 바꾸어 푸는 것 이론 파라메트릭 서치 (Parametric search)는 이분 탐색(binary search)의 일종으로 선형 탐색에 비해 효율적인 시간 복잡도를 가집니다. 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정문제 로 바꾸어 푸는 것이라고도 할 수 있습니다. 어떤 명제 에 대해 True와 False의 경곗값 v0를 찾아야 할 경우 파라메트릭 서치를 이용하게 됩니다. 중간 위치는 (0+8)/2 =4 이므로, p(4)를 확인해보니 True -> 4는 v0의 후보군이 되고, 5~8은 탈락. 다음 중간 위치는 (0+3)/2 =1 이므로,p(1)을 확인해보니 False -> 0~1은 탈락. 다음 중간 위치는 (2+3.. 2020. 12. 16. 이전 1 다음
