[132] 매개변수 탐색(parametric search)

1. 매개변수 탐색이란?

영어로 parametric search라고도 부르는 이 탐색 알고리즘은 이진 탐색과 유사합니다.

이진 탐색을 하기 위해서는 데이터가 정렬되어 있어야 가능한데, 매개변수 탐색도 마찬가지로 데이터 안에서 한 요소를 기준으로 어느 한 쪽의 결과가 일정해야 합니다.

이런 상황에서 조건을 만족하는 최대값 혹은 조건을 만족하지 않는 최소값을 찾을 때 유용하게 사용됩니다.

https://en.wikipedia.org/wiki/Parametric_search

Parametric search - Wikipedia

 

예를 들어 여러 명의 사람이 남자와 여자로 나뉘어 한 줄로 서있다고 해봅시다.

이 때, 무작위로 어떤 사람을 선택하더라도 그 사람이 남자면 그 사람보다 왼쪽에 있는 사람은 모두 남자고, 그 사람이 여자면 그 사람보다 오른쪽에 있는 사람은 모두 여자입니다.

따라서 남자와 여자가 나뉘는 부분을 찾기 위해서 반씩 나눠가며 탐색하면 됩니다.

아래의 예시를 보면 단 네 번만에 찾을 수 있는 것처럼 반 씩 나눠가며 찾기 때문에 시간복잡도도 이진 탐색과 마찬가지로 \(O(\log{n})\)입니다.

이렇게 맨 마지막 남자(남자인 최대값) 혹은 맨 처음 여자(남자가 아닌 최소값)를 찾을 때 매개변수 탐색을 사용할 수 있습니다.

2. 매개변수 탐색을 적용할 수 있는 문제

위 예시의 남자인가? 혹은 여자인가? 와 같은 결정 문제를 적용할 수 있는 문제이면서,

어떤 부분까지는 조건에 만족하지만 그 뒤로는 조건이 만족하지 않는 경우에 최대값이나 최소값을 찾는 문제에 적용해볼 수 있습니다.

3. 매개변수와 결정함수

매개변수 탐색은 위에서 살펴본 것과 같이 범위의 가운데를 살펴보고 방향을 정해 반씩 나누어 가면서 탐색하는 알고리즘입니다.

탐색에 사용되는 값을 매개변수라고 하며 매개변수는 정한 범위의 중간값이 됩니다.

범위를 좁히기 위해 매개변수가 조건에 참인지 거짓인지 판별하는 함수를 결정함수라고 합니다.

따라서 매개변수 탐색을 문제에 적용하기로 하였다면, 그 문제에서 매개변수와 결정함수를 바르게 설정하는 것이 매우 중요합니다.

4. 매개변수 탐색과 이진 탐색의 차이점

이진 탐색의 경우 찾고자 하는 특정 값으로 탐색하지만, 매개변수 탐색은 조건이 변하는 부분의 최대값(혹은 최소값)을 탐색합니다.

따라서 이진 탐색은 탐색 도중에 원하는 값이 발견되면 바로 종료되지만,

매개변수 탐색은 결국 탐색할 중간값(매개변수)이 존재하지 않는 범위까지 탐색하게 됩니다.

5. 매개변수 탐색 방법

우선 문제를 파악하고 매개변수를 탐색할 범위를 올바르게 설정합니다.

문제의 조건을 파악하여, 매개변수에 따라 참/거짓을 반환하는 결정함수를 구현합니다.

매개변수를 결정함수에 대입한 결과를 가지고 범위를 좁혀가면서 탐색합니다.

결국 마지막엔 조건이 달라지는 두 요소(위 예시에서는 마지막 남자와 처음 여자)가 범위가 됩니다.

찾고자 하는 값이 최대값인지, 최소값인지에 따라 마지막 범위의 왼쪽 값 혹은 오른쪽 값을 취합니다.