[Algorithm] 이분탐색(Binary Search) vs 매개변수 탐색(Parametric Search)

# 요즘 스터디에서 이분탐색을 주제로 한 문제들을 풀다 내가 풀이 하고 있는 방식이

   '이분탐색'이 아니라는 것을 깨달았다. 아예 다른 것은 아니지만,

    엄밀히 따지자면 '매개변수 탐색'이라는 분류가 따로 존재했다.

 

# 이분탐색은 '정렬된 배열'에서 target의 존재여부와 존재한다면 위치를 알려주는 알고리즘이다.

   우리가 찾는 target이 배열 안에 존재한다면, 그 위치를 알려준다는 것이다.

   

# 하지만, 'target과 정확히 일치하는 값' 이 존재하지 않는다면??

    -> 우리는 parametric search를 통해 최적화된 값을 찾을 수 있다.

 

# Parametric Search는 최적화 문제를 결정 문제로 풀 수 있는 기술이다.

   '최적화 문제'니 '결정 문제'니 다 처음 들어보는 말이어서 어려울 수 있다.

   * 최적화 문제: 문제의 답이 하나가 아니라 여러 개이고, 그 중에서

                             어떤 기준에 따라 가장 '좋은' 답을 찾아내는 문제

   * 결정 문제: '예' 혹은 '아니오' 형태의 답만이 나오는 문제

                      ( ‘답 x가 존재하는가?’ 대신 ‘x 또는 그보다 좋은 답이 있는가?’ )

   * 최적화 문제의 답은 경우의 수가 무한한 데에 반해, 결정 문제는 두 가지 답만이 있을 수 있음

 

# 최적화 문제 결정 문제로 바꾸기 레시피
    1.  ‘가장 좋은 답은 무엇인가?’ 라는 최적화 문제를

                    ‘x 혹은 그보다 좋은 답이 있는가?' 라는 결정 문제 형태로 바꿈
    2.  결정 문제를 쉽게 풀 수 있는 방법이 있는지 찾아보기
    3.  결정 문제를 내부적으로 이용하는 이분탐색 알고리즘 작성

 

# 매개변수 탐색 예시

  *  https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 위 문제는 가장 인접한 두 공유기 사이의 최대 거리를 출력하는 문제이다.

 단순히 이분 탐색으로 '구하고자 하는 값'을 찾는 것이 아닌 '최대 거리'를 찾음으로써 최적화된 값을

 도출해 내는게 목표이다. 

 

# 이분탐색 예시

  * https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 위 문제는 배열 A안에 x라는 정수가 존재하는지 판단하는 문제이다.

 단순히 이분탐색을 통해 '구하고자 하는 값'을 찾아내면 되는 문제이다.

 

 

# 결론적으로, Binary Search와 Parametric Search의 차이점은

   Binary Search에서는 배열에서 X와 일치하는 값을 찾으면 바로 함수를 종료하고 위치를 반환하지만

   Parametric Search는 함수를 종료하지 않고 더 이상 살펴볼 배열이 남아있지 않을때까지 탐색을 계속한다.