매개 변수 탐색 (Parametric Search)
이진 탐색(이분 탐색)을 사용하여 조건을 만족하는 최대값/ 최솟값을 구하는 방법
매개 변수 탐색 vs 이진 탐색
- 이진 탐색 : target과 일치한 값을 찾으면, 함수를 종료하고 위치 반환
- 매개 변수 탐색 : target과 일치하는 값을 찾아도 함수를 종료하지 않고 더이상 탐색할 배열이 남아있지 않을 때까지 탐색을 계속한다.
시간복잡도는 둘 다 O(logN)으로 동일하다.
과정
- 정답을 매개 변수로 만들고, Yes/No 문제(결정 문제)로 바꿔 보기
- 모든 값에 대해서 Yes/No를 채웠다고 생각했을 때, 정렬된 상태인가?
- Yes/No를 결정하는 문제로 풀기
- 문제에서 최종적으로 찾고자하는 최솟값/최댓값을 매개변수로 본다.
- 결정 함수를 정의하고 구현했을 때 결과 배열이 연속인지 확인한다.
- 최솟값이면 결정 함수의 결과가 [f,f,...,t,t] 에서 f->t 로 바뀌는 부분을 찾는다.
- 최댓값이면 결정 함수의 결과가 [t,t,...,f,f] 에서 t->f 로 바뀌는 부분을 찾는다.
의의
- 문제를 거꾸로 푸는 것이기 때문에 통찰력이 요구된다.
- 최근 코딩테스트 빈도로 굉장히 높게 나온다.
- 키워드에 "~~의 최댓값/최솟값 을 구하시오"가 포함되면 매개 변수 탐색을 접근해볼 가치가 있다.
예제
땅콩의 모험 (server)