최적화 문제를, 결정 문제로 바꿔서 이진탐색으로 푸는 방법
*최적화 문제 : 문제 상황을 만족하는 변수의 최솟값 또는 최댓값을 구하는 문제 (ex. 최단 경로 문제)
*결정 문제 : Yes 또는 No 를 구하는 문제
수강생들의 외모값(외모를 수치화할 수 있는 기계가 생겼다고 가정하자..)과,, 커플/솔로 여부가 주어진다..
커플들은 항상 솔로들보다 외모값이 높다고 가정하자..
그럼 외모 값이 최소 몇 이상일 때부터 커플인가?
회원
외모값. 커플 여부.
커플?
외모값?
| 회원 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 커플여부 | F | F | F | T | T | T | T | T |
| 외모값 | 2 | 4 | 5 | 6 | 6 | 7 | 9 | 10 |
- "파라메트릭"은 **"파라미터(변수)"**에 의존하는 문제를 해결하는 접근법을 나타냅니다.
- 일반적으로 문제를 단순히 해답을 찾는 방식으로 접근하지 않고, 특정 변수(파라미터)의 범위를 조정하면서 해를 구하거나 최적값을 탐색합니다.
그래서 parametric 접근법이라고한다.
우선 중간값인 6이 T이므로, 오른쪽은 다 T일 것이므로 생각할 필요가 없다.
좌측 배열의 중간값인 5가 F이므로, 좌측은 다 F일 것이므로 생각할 필요가 없다.
이런식으로, 최소 몇 이상일 때부터 T인지 찾아나간다.
파라메트릭 서치에는 몇가지 조건이 필요하다.
1. 매개변수가 주어지면 true or false가 결정되어야한다.
2. 가능한 해의 영역이 연속적이어야 한다.
3. 범위를 반씩 줄여가면서 가운데 값이 true인지 false인지 구한다
4. 이진탐색과 똑같은 원리
이진탐색은 특정값을 찾는 거라면, parametric 서치는 경계값을 찾는 경우가 많다.
파라미터가 주어지면, 이때 반환값이 T인지 F인지 반환하는 함수도 필요하다. 이 함수를 기반으로 왼쪽을 더 탐색할지, 오른쪽을 더 탐색할지 판단한다.