글 읽기 - 삼분탐색에서 왜 기준점을 삼등분점으로 잡나요?

[S,E]에서 삼분탐색을 돌 때 [S,E]에 속하는 어떤 두 기준점 L, R (L<R) 의 값을 비교해서 구간을 [S,R] 또는 [L,E]로 축소시킬 수 있는 거잖아요.

그런데 생각해 보면 보통 삼분탐색을 할 때 L, R을 S, E의 삼등분점으로 잡고 이 때 구간의 길이가 2/3으로 줄어드는데, L, R을 가운데에 몰아서 잡으면 구간이 1/2정도로 줄어드는 것 아닌가요?

사실 L, R을 가운데에 몰아서 잡는 것은 기울기로 이진탐색하는거랑 동치인데 이렇게 생각해 보면 도대체 삼분탐색을 해서 좋을 게 뭔지 모르겠네요.

삼분탐색에서 왜 기준점을 삼등분점으로 잡나요?

볼록함수를 기울기로 이진탐색하고 싶으시다면 도함수를 구해야만 합니다. 보통은 이게 쉽지 않아서, 삼분탐색을 사용합니다.

음... 기울기로 이진탐색한다는 표현에서 조금 오해가 있었던 것 같은데요,

요점은 삼분탐색에서 피벗을 가운데에 몰아잡는 것이 삼등분점으로 잡는 것보다 낫지 않나? 입니다.

오차가 있을 경우 3등분으로 잡는게 좀더 안전하고, 실제로 볼록하지 않더라도... 대충 볼록하다면 3등분 삼분탐색이 잘 먹히기도 합니다.

시간제한이 빡빡하다면 2/5, 3/5 점이나, 10/21, 11/21 등으로 잡는 것도 좋습니다.

오차에 대해 추가 설명을 하자면, f(x)와 f(x+σ)를 구분하기 힘들다고 할 때, 10/21, 11/21로 한다면 high-low < 21σ일 때 다음 스텝이 틀릴 수 있습니다.

반면 3등분 탐색의 경우 high-low > 3σ면 다음 스텝이 보장되므로 좀더 안전해요.

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge