파라메트릭 서치

파라메트릭 서치

● 최적화 문제를 결정 문제로 바꿔서 이진탐색으로 푸는 방법

● 매개변수 Parameter가 주어지면 true or false가 결정되어야 한다.

● 가능한 해의 영역이 연속적이어야 한다.

● 범위를 반씩 줄여가면서 가운데 값이 true 인지 false 인지 구한다.

● 이진탐색과 똑같은 원리

 

 

최적화문제 Optimazation Problem

- 문제 상황을 만족하는 변수의 최솟값, 최댓값을 구하는 문제

결정 문제 Decision Problem

- Yes/No Problem

 

Q(파라메트릭 서치 예시). 큔콴이 대학생들의 외모값과 커플/솔로 여부가 주어진다.커플들은 솔로들보다 외모값이 높다.(^^) 외모값이 최소 몇 이상일 때부터 커플인가?

외모값에 따른 커플 여부