Parametric Search

1. Parametric Search란 무엇일까?

파라매트릭 서치는 최적화 문제를 결정 문제로 바꾸어 풀어나가는 탐색 알고리즘입니다.

주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘. 주어지는 값이 범위이기 때문에 특정한 상황을 최적화 시키는 문제에 용이.

최적화 문제?
최적화 문제(Optimization)는 가능한 해들 중에서 가장 좋은 (최대 또는 최소)의 해를 찾는 문제를 말합니다.

결정문제?
true or false로 대답이 가능한 문제를 말합니다.
x > 5 인가에 대하여 true인지 false인지 정확하게 답이 나오게 되는 문제를 말합니다.

예시
[-5,-1,-2,-10,8,1,4,10,11,8]에서 "양수의 최소 Index를 찾으시오"라는  최적화 문제를 풀어봅시다.
'해당Index를 선택하면 양수인가?'하는 결정문제로 바꾸어 찾을 수 있고 이 과정은 이진 탐색으로 이루어집니다

또 다른 예를 들어자면, 정육점에서 고기 200g을 달라고 해봅시다.
고기 덩어리에서 200g을 덜어낸다고 했을 때, 바로 200g을 잘라내는데는 어려움이 있으니까 일정 부분을 덜어내서 무게를 잰 다음, 덜어내거나 추가하는 식으로 200g을 맞추는 식으로 주어진 문제 또는 요청에서 주어진 문제를 200g보다 많나 적나 하는 결정문제로 변형하여 풀어나가는 식입니다.

2. Parametric Search를 이해해보자.

Parametric seach를 이해하기 위해서 중점적으로 봐야하는 점은 두가지 라고 생각합니다.

1. 결정 문제로의 변화

2. 'Search'

 

최적화문제를 결정 문제로 변경해봅시다.

"최대 해를 찾아주세요"-> "가능한 해" 들 중에서 가장 최대 해를 찾아주세요 

-> X가 "가능한 해"일 때 이 해는 최대인가요? -> 'X'는 가능한 해인가요?

 

결정 문제로 true인가 false인가를 구별할 수 있게 되었습니다. 
그렇다면 우리는 이제 'Search'를 해야합니다. 가능한 X들 중에서 최대의 X를 찾아가야 하는 것이죠.

어떠한 값을 빠르게 search하는 방법 중에서 이분탐색을 활용한다면 O(logN) 시간복잡도에 찾아낼 수 있습니다.

 

정리하자면,

 1. 최적화 문제를 결정문제로 변경해본다. ('X는 가능한 해인가요?')

 2. 결정문제를 반복적으로 물어보면서 최대 X를 찾아본다 ('search by 이분탐색')

 

3. 그럼 언제 Parametric Search를 사용할 수 있죠? (조건)

Parametric Search에서는 빠르게 탐색하기 위해 이분탐색을 사용한다고 했습니다.

이분탐색을 하기 위한 조건은 '정렬되어 있다' 와 'Random access' 입니다.

그럼 Parametric Search 또한 이분탐색을 하기 위한 조건을 만족해야합니다.

 

그래서 보통

1) 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우

2) 어떠한 정렬된 해의 집합에서 최적화 문제의 해를 기준으로 나뉘는 경우

  즉, 최소 값이 X라면, X이상에 대해서는 모두 조건을 만족

       최대 값이 X라면, X이하의 값에 대해서는 모두 조건을 만족

[ 그림 2]

저는 조건의 핵심은 " 연속성이 있는 해"라고 생각합니다.

parametric search 자체가 '결정문제를' 반복적으로 확인해가면서 답의 범위를 좁혀나가는 방법이기 때문에

[그림 2]처럼 '조건'에 따라 결정문제의 범위가 true 와 false로 구분이 되어야 합니다.

그 때 경계에 도달하는 값(최적화의 해)를 찾는 과정이라고 이해하시면 됩니다.

 

 

그래서 Parametric Search를 알고리즘 문제를 풀면서 적용하기 위해서는 주어진 문제를 결정문제로 잘 정의하는 것이 가장 핵심이라고 할 수 있습니다.

 

    

 

 관련 문제들을 풀면서 든 생각은 다음과 같습니다.

이런 조건이라면? 이런 아이디어 또는 생각이 든다면?

• 문제에서 구하고자 하는 답의 범위가 (상한 또는 하한) 명확하게 정해져 있다.
• 그 범위가 너무 커서 도저히 하나씩 대조해 볼 수 없다.
• 결과 값은 항상 경향성/방향성을 갖는다
• 범위에 있는 수가 균일하고 연속적이다.

라고 한다면 Parametric Search를 고려할 수 있습니다.

 

 

4. 구현을 해봅시다.

parametric search의 구조는 binarySearch와 같기 때문에 간단합니다.

하지만, binary search에서 "==" 부분이 이제 결정문제로 치환된다고 생각하시면 됩니다.

 

구현시 고려할점은 밑의 링크들에 자세히 소개 되어 있습니다.

https://www.acmicpc.net/blog/view/109

 

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

https://blossoming-man.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search-%EA%B2%BD%EA%B3%84-%EC%84%A4%EC%A0%95%EC%9D%84-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%B4%EC%95%BC-%ED%95%98%EB%8A%94%EA%B0%80

이진 탐색 Binary Search 경계 설정을 어떻게 해야 하는가

 

구현은 문제를 풀면서 보는 것이 가장 이해가 잘 되기 때문에 추가적으로 link를 걸어두겠습니다.

 

블로그 안에 있는 parametric search 활용 문제

[백준 Q2473] 세 용액

 

 

 

관련 문제 풀어보기 

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

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

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