Ternary Search (1) 썸네일형 리스트형 39. Ternary Search 삼분 탐색(Ternary Search)은 어떤 데이터가 극값 하나를 가지는 형태로 나열되어 있을 때 그 극값을 빠르게 찾을 수 있는 탐색 방법이다. 일반적으로 데이터 자체를 삼분 탐색으로 찾을 일은 거의 없고, 어떤 함수의 개형이 특정 구간에서 볼록함수로 나타내어질 때 극값을 찾기 위해 삼분 탐색이 사용되는 경우가 많다. 삼분 탐색을 삼진 탐색이라고 하는 경우도 있으나 삼진 탐색이라는 용어는 잘 쓰이지 않는 것으로 보인다. 다음과 같은 함수 $f(x)$의 극값을 찾는 상황을 생각해 보자. $f(x)$가 극값을 갖는 $x$의 범위를 알고 있고, 임의의 $x$에 대해 $f(x)$를 구할 수 있다고 가정한다. 이 함수는 주어진 구간에서 하나의 극값을 가지므로 삼분 탐색을 사용할 수 있다. 먼저 주어진 구간을 .. 이전 1 다음
