삼분탐색 (2) 썸네일형 리스트형 백준 8986. 전봇대 기본적인 삼분탐색 문제, 처음엔 단순 이분법 parametric search로 푸는 문제인줄 알고 한참을 고민했다. 삼분탐색으로 풀 생각을 하고 삼분탐색에 대해 살짝 맛을 봤더니 삼분탐색도 이분탐색으로 하는 방법이 있길래 풀어보았다. 삼분탐색에 대한 정리는 https://mingnine9999.tistory.com/34에 해두었다. https://www.acmicpc.net/problem/8986 8986번: 전봇대 입력의 첫 줄은 전봇대의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄에는 전봇대의 위치를 나타내는 N개의 서로 다른 x-좌표 xi(i = 0, ..., N-1)가 빈칸을 사이에 두고 오름차순으로 주어진다. xi는 www.acmicpc.net 전봇대들을 모두 같은 거리만큼 .. 삼분탐색..!!(Ternary search) 보통 이분탐색(binary search)에 대해서는 기본적으로 알고있는 경우가 대부분이다. 하지만 삼분탐색(ternary search)라면 어떨까?! 이분탐색은 정렬되어 있는 수열 속에서 원하는 값을 찾을 때 사용 할 수 있는 탐색 기법이다. 즉, 단조 증가 또는 단조 감소 수열에서 내가 원하는 값이 있는지 없는지를 판단하는 경우에 쓰인다. 삼분탐색은 조금 다른데 오목하거나 볼록한 수열에서 극값을 찾는 탐색이다. 하지만 오목 볼록이 여러번 반복되거나 평평한 (같은 값이 반복되는) 수열에서는 값을 찾을 수 없다. 예를들어, 그래프를 그렸을 때 밑에 그림처럼 나오는 수열에 적용 가능하다. 정석적인 삼분탐색의 방법은 극대값을 찾는다 했을 때, 양쪽끝을 기준으로 1/3지점과 2/3지점을 비교하여 둘 중 더 작거.. 이전 1 다음
