[Algorithm] 매개 변수 탐색 (Parametric Search)

1. 매개 변수 탐색 (Parametric Search)

최적화 문제를 결정 문제로 바꾸어 푸는 것이다.

• 정답을 파라미터로 만들고 결정문제로 바꾸어 푼다 => 이분 탐색의 아이디어

배열이 0과 1만 존재하며 오름차순 인건 보장되지만, 전체 배열은 모른다.
특정 인덱스의 값을 O(T)에 계산 가능할 때, 여기서 0과 1의 경계를 찾아야 한다면?

Up-Down 게임

• A가 1~1000 사이의 어떤 자연수를 선택
• B는 A 한테 "생각한 숫자가 X 이상이야? 라는 질문
• A는 맞으면 1, 아니면 0 이라고 대답
• 최소 횟수로 질문하려면?

• 하나씩 탐색 : 1000번 탐색, T(탐색시간) => O(T * 1000)
• 이분 탐색 : log1000 탐색, T(탐색시간) => O(T * log1000) = O(T * 10)

* 매개변수 탐색의 전환

• 이분 탐색시 하나를 값을 선택(C)을 한다. (정답을 파라미터로 생각한다, 이분탐색)
  • C가 X보다 작다면 C보다 작은 값들은 전부 No (결정 문제)
  • C가 X보다 크다면 C보다 큰 값들은 전부 No (결정 문제)

 

3. 매개 변수 탐색 접근

• 1) 정답을 "매개 변수(Parameter)"로 만들고 Yes/No 문제(결정 문제)로 바꿔 보기
• 2) 모든 값에 대해서 Yes/No를 채웠다고 생각했을 때, 정렬된 상태인가?
• 3) Yes/No 결정하는 문제를 풀기

 

4. 자주 하는 실수

• 1) 매개 변수에 대한 결정이 Nooooooo Yesssssss 꼴이 아닌데 이분 탐색을 하는 경우
• 2) L, R, M, Result 변수의 정의를 헷갈려서 부등호 등을 잘못 쓰는 경우
• 3) L, R 범위를 잘못 설정하거나 Result의 초기값을 잘못 설정하는 경우

 

5. Tip

• 아래의 키워드가 있다면 매개변수 탐색 접근을 시도해볼 가치가 있다. 
  • 최댓값을 구하시오
  • 최솟값을 구하시오