삼분 탐색(Ternary search)

아직은 기본기만 사용할 줄 알고 특정한 경우에 대한 반례들이 있어 (ex: 평평한 구간에 최솟값, ..)

삼분 탐색을 알고 있다고 말하기는 힘들지만 이해할려고 노력했기 때문에 조심스럽게 글을 써봅니다

 

https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221432986308&proxyReferer=https%3A%2F%2Fwww.google.com%2F

삼분탐색에 대한 공부는 여기서 했으며 정리를 매우 잘해놓으셨으니 제 포스트 보다는 여길 참고하시는게 좋습니다.

 

삼분탐색은 이분탐색과 같은 원하는 값을 위한 증감 범위를 이용한 탐색인데

이분탐색은 정렬이 되어있기 때문에 반드시 임의의 값을 기준으로 한군데는 증가한다면 반대는 감소하는 형식입니다.

말그대로 일차방정식의 직선과 같은 그림을 상상해볼 수 있습니다.

 

반대로 삼분탐색은 어떤 원하는 값들의 형태가 직선형태의 무조건적인 증감을 말하는게 아닌

아래나 위로 볼록한 형태의 특성을 띄는 값들 중에서 원하는 값을 찾기 위해 사용할 수 있는 탐색방법 입니다.

이 탐색방법을 이용하여 이분탐색보다 구체화(?) 된 조건으로 이 볼록한 구간내의 원하는 값을 탐색해나갈 수 있습니다.

이해를 위해 그림으로 설명해보면, 

 

 

이와 같이 표현할 수 있고, 이 볼록한 구간을 이용하기 위해

fp, lp 그리고 삼등분한 p1, p2 를 구하게 된다면

p1 과 p2 를 이용하여 이 곡선(방정식)에 대한 함수값을 구할 수 있게 됩니다.

 

곡선의 식을 Func 라고할때

Func(p1) 의 값이 Func(p2) 보다 작은 경우 알 수 있는 사실은

구간 [p2,lp] 에 존재하는 최소값은 구간 [fp,p2] 에 존재하는 최소값보다 작을 수 없다 입니다.

=> 만약 볼록 구간 중에서 최소값을 찾고자 한다면 구간 [fp,p2] 의 범위를 탐색해야한다 는 뜻입니다.

 

이를 이용하여 fp 와 lp 를 원하는 조건에 맞게 p1 p2 값으로 바꾸어주면서 탐색하는 방법이 삼분 탐색입니다.

 

삼분탐색을 이용한 문제는

BOJ : https://www.acmicpc.net/problem/11662 민호와 강호

BOJ : https://www.acmicpc.net/problem/13310 먼 별

BOJ : https://www.acmicpc.net/problem/8986 전봇대 

등이 있으며

민호와 강호 문제가 삼분탐색을 이용한 문제 중에 제일 기초? 문제 인듯 싶으니 풀어보시면 좋을 것 같습니다.

(삼분탐색으로 안해도 해결가능합니다!)

 

삼분 탐색을 설명했는데 미흡한 부분이나 틀린 부분이 있다면 지적부탁드립니다!