Ternary Search
in Algorithms
Ternary Search 알고리즘에 대해 설명하는 페이지입니다.
Environment
- OS: Windows 11
목차
Introduction
- Definition
- 삼분 탐색(Ternary search) 은 이분법이 매 반복마다 답의 후보 구간을 절반으로 잘라 각 위치에서 함수의 값을 계산하는 것과 비슷하게, 답의 후보 구간을 삼등분하는 두 위치에서 함수의 값을 계산하는 탐색 방식이다.
- 삼분 탐색은 볼록 함수(Convex function) 또는 오목 함수(Concave function) 에서 극값, 또는 최대/최소 값을 찾을 때 유용하게 사용되는 기법이다.
- 삼분 탐색은 한 번 반복할 때마다 후보 구간의 크기를 2/3로 줄여나간다.
- 그래프를 갖는 함수의 최대점을 찾는 문제는 여러 가지 방법으로 풀 수 있다. 함수를 직접 미분하거나, 국소 탐색 알고리즘 등으로 해결할 수 있다. 그러나 삼분 탐색은 미분할 수 없는 함수에도 사용할 수 있으며, 국소 탐색에 비해 훨씬 빠르게 동작하고 수렴 판정이 용이하기 때문에 더 자주 사용된다.
국소 탐색(Local search) 은 임의의 답을 하나 만들어 놓고 이 값을 조금씩 갱신하면서 답이 더 좋아지는 쪽으로 움직이는 알고리즘이다.
Examples
