파라매트릭 서치(Parametric Search)

---

목차

1. 파라매트릭 서치(Parametric Search)란?

2. 예시를 통한 파라매트릭 서치(Parametric Search)

3. 시간 복잡도

4. 정리

5. 관련 문제

---

1. 파라매트릭 서치(Parametric Search)란?

Parametric Search에 대해 알아보자.

파라매트릭 서치는 이분 탐색과 매우 유사하다.

하지만 파라매트릭 서치와 이분 탐색의 차이점을 알게 된다면, 둘의 차이를 느낄 수 있게 되고, 파라매트릭 서치를 더 유용하게 쓸 수 있을 것이다.

파라매트릭 서치는 다음과 같이

'최적화 문제를 결정 문제로 바꾸어 푸는 것이다.' 라고 정의 할 수 있다.

무슨 말인가 한번 생각해보자.

2. 예시를 통한 파라매트릭 서치(Parametric Search)

문제)

자동차를 탈 수 있는 사람중 나이가 가장 어린 사람을 찾고자 한다.

이때 자동차를 탈 수 있는 사람이라 함은 나이가 19세 이상이라고 가정한다.

(즉, 19세 이상은 모두 탈 수 있다고 한다.)

가장 어린 사람의 번호는 몇번인가?

전제)

사람이 나열되어있고 이 사람들은 나이순으로 정렬되어있다.

이렇게 문제가 주어진다면, 이 문제를 결정 문제로 바꿀 수 있을까?

결정 문제로 바꾸어보자.

-> 자동차를 탈 수 있나요?

이제 결정 문제로 바꾸었으니 이 문제를 해결할 수 있는지 접근해보자.

만약 문제가 이 방법론으로 접근 할 수 있고 해결 할 수 있다면 파라매트릭 서치를 정확히 썼다고 할 수 있다.

앞서 말했듯이 파라매트릭 서치(Parametric Search)는 이분 탐색과 매우 유사하며 결정 문제로 푸는 것이라 하였다.

따라서 Left와 Right를 두어 문제를 풀어보자.

첫번째 위의 그림에서는 5번 사람이 자동차를 탈 수 없다 하였다.

전제에서 이미 나이순으로 정렬되어 있다고 했으니 5번 이하 사람들은 모두 이제 정답 범위에서 벗어나게 된다.

이제 두번째 그림을 보자. 5번까지는 이미 정답 범위에서 제외되었으니 6이 Left, 9가 Right가 될 것이다.

이때 Mid는 7이 될것이고 7에게 질문을 해본다.

7은 자동차를 탈 수 있다고 한다.

문제의 가정에 의해 19세 이상은 자동차를 탈 수 있고 나이순으로 정렬되어 있으니 7번 이후의 사람들은 모두 정답 후보에 포함된다.

그렇다고 7번이 자동차를 탈 수 있는 가장 어린사람이라고 할 수 있을까? 그렇지 않다.

5번 이하까지만 모두 정답 범위에서 제외될 뿐, 6번에 대한 정보가 아직 없다.

따라서 Left와 RIght를 다시 조절해야한다.

위의 그림처럼 Left와 Right가 6을 향하게 될 것이고, 결국 Mid가 6이 되어 6을 타겟으로 질문을 하게 된다.

만약 여기서 6이 자동차를 탈 수 있나요의 질문에 네라고 반응한다면 정답은 6이 될 것이고, 아래 그림처럼 아니오라고 말한다면 정답은 7이 될 것이다.

3. 시간 복잡도

파라매트릭 서치(Parametric Search) 또한 이분탐색 처럼 L, R을 두고 Mid에 대한 판별을 이용하기에

결국 이분탐색과 마찬가지로 O(lgN)의 복잡도를 가지게 된다.

4. 정리

- 파라매트릭 서치는 이분 탐색과 매우 유사하다.

     - 이때 이분 탐색 문제와 차이점을 말하자면 결정 문제인지 아닌지의 차이이다.

- 위의 그림을 통한 설명을 봐서도 알 수 있듯이 파라매트릭 서치로 인해 정답 후보가 나타나면 연속적으로 정답후보가 나타난다.

- 파라매트릭 서치 시간 복잡도는 O(lgN)이다.

5. 관련 문제

[2110번] 공유기 설치 :: https://www.acmicpc.net/problem/2110

[1654번] 랜선 자르기 :: https://www.acmicpc.net/problem/1654

[2613번] 숫자 구슬 :: https://www.acmicpc.net/problem/2613