---
title: "꼭짓점은 양 끝이 아니라 두 점을 비교해서 찾는다"
description: "올라갔다 내려오는 곡선의 최고점을 찾는 문제입니다. 크다 작다로는 방향을 알 수 없어서, 가운데 두 점을 견줘 삼분의 일씩 버립니다. 그 전제가 깨지는 자리까지."
author: "유니얼"
pubDate: 2026-09-16
updatedDate: 2026-09-18
category: "programming/algorithm/search"
tags: ["탐색"]
canonical: https://blog.unialgames.com/posts/algo-ternary-search/
---
투사체를 던지는 각도를 정합니다. 각도를 올리면 사거리가 늘다가 어느 지점을 넘으면 다시 줄어듭니다.
가장 멀리 날아가는 각도를 찾고 싶습니다.

이분 탐색이 안 됩니다. 한 점을 보고 "여기가 찾는 값보다 크다" 를 알아도 **왼쪽으로 가야 할지 오른쪽으로 가야 할지 모릅니다.**
올라가는 중일 수도 있고 내려오는 중일 수도 있으니까요. 한 점만으로는 방향이 안 나옵니다.

## 두 점을 비교하면 방향이 나온다

구간 안에 점을 둘 잡습니다. 왼쪽 점을 `m1`, 오른쪽 점을 `m2` 라고 하면 비교 결과가 이렇게 읽힙니다.

| 비교 | 알 수 있는 것 | 버리는 곳 |
| --- | --- | --- |
| `f(m1) < f(m2)` | 꼭짓점은 `m1` 보다 오른쪽에 있다 | `m1` 왼쪽 |
| `f(m1) > f(m2)` | 꼭짓점은 `m2` 보다 왼쪽에 있다 | `m2` 오른쪽 |

왜 그런지는 곡선이 하나의 봉우리라는 전제에서 나옵니다.
`m1` 이 `m2` 보다 낮다면 `m1` 은 아직 올라가는 구간에 있다는 뜻이고, 꼭짓점이 그 왼쪽에 있을 수는 없습니다.

두 점을 구간의 삼등분 자리에 두면 한 번 비교에 **구간의 삼분의 일**이 사라집니다.
이 방법의 이름이 **삼분 탐색(ternary search)** 이고, 봉우리가 하나인 함수는 단봉 함수(unimodal function)라고 부릅니다.

```csharp
float lo = 0f, hi = 90f;            // 각도 범위

for (int i = 0; i < 100; i++) {
    float m1 = lo + (hi - lo) / 3f;
    float m2 = hi - (hi - lo) / 3f;

    if (Range(m1) < Range(m2)) lo = m1;
    else                       hi = m2;
}

return (lo + hi) / 2f;
```

실수 범위라 종료 조건 대신 **반복 횟수를 고정합니다.** 한 번에 삼분의 이가 남으니 백 번이면 어떤 범위든 충분히 좁혀집니다.
매 회 `f` 를 두 번 부르는 것이 비용입니다. 계산이 무거우면 이전 회차의 값을 하나 재활용하는 변형도 있습니다.

## 기울기를 보면 이분 탐색으로도 된다

같은 문제를 이분 탐색으로 푸는 방법도 있습니다. **값이 아니라 기울기의 부호**를 보는 것입니다.

봉우리가 하나면 기울기는 꼭짓점 전까지 양수이고 그 뒤로는 음수입니다.
한 방향으로만 바뀌니, 기울기가 음수로 바뀌는 첫 지점을 찾는 이분 탐색이 됩니다.

```csharp
if (f(mid) < f(mid + eps)) lo = mid;   // 아직 올라가는 중
else                       hi = mid;   // 이미 내려가는 중
```

한 번에 절반이 사라지니 삼분 탐색보다 덜 돕니다. 대신 `eps` 를 얼마로 둘지가 새 문제가 됩니다.
너무 작으면 두 값의 차이가 부동소수 오차에 묻혀서 부호가 뒤집힙니다.
**정수 범위라면 `f(mid) < f(mid + 1)` 로 쓸 수 있어서 이쪽이 더 깔끔합니다.**

## 정수 구간에서 생기는 함정

삼분 탐색을 정수로 옮기면 구간이 줄지 않고 멈추는 자리가 생깁니다.
칸이 두세 개 남으면 `m1` 과 `m2` 가 같은 칸을 가리키면서 `lo` 와 `hi` 가 그대로 유지됩니다.

그래서 정수 버전은 **끝을 손으로 처리합니다.**

```csharp
while (hi - lo > 2) {
    int m1 = lo + (hi - lo) / 3;
    int m2 = hi - (hi - lo) / 3;
    if (f(m1) < f(m2)) lo = m1 + 1;
    else               hi = m2;
}

// 남은 두세 칸은 그냥 전부 계산해서 고른다
int best = lo;
for (int i = lo + 1; i <= hi; i++)
    if (f(i) > f(best)) best = i;
```

몇 칸 남았을 때 훑는 비용은 상수라 전체 비용을 바꾸지 않습니다.
**경계를 억지로 맞추기보다 마지막 몇 칸을 포기하는 쪽이 버그가 적습니다.**

## 봉우리가 하나일 때만 성립한다

이 방법이 기대는 것은 곡선이 **올라갔다 내려오는 모양 하나**라는 전제입니다. 봉우리가 둘이면 답이 엉뚱하게 나옵니다.

```
      ∧         ∧
     /  \      /   \
    /     \__/       \
   왼쪽 봉우리   오른쪽 봉우리
```

두 점이 각각 다른 봉우리에 걸리면 비교 결과가 "더 높은 쪽으로 가라" 를 말해 주지 않습니다.
운이 나쁘면 진짜 최고점이 있는 구간을 통째로 버립니다.

게임에서 이 전제가 깨지는 자리가 흔합니다.

- **여러 효과가 겹칠 때.** 스탯 배분처럼 임계값이 여럿이면 곡선에 혹이 여러 개 생깁니다
- **계단이 있을 때.** 값이 구간마다 뚝뚝 끊기면 평평한 구간에서 두 점이 같은 값을 냅니다
- **측정으로 값을 얻을 때.** 흔들리는 측정값은 봉우리를 가짜로 만듭니다

곡선의 모양을 모르겠으면 **먼저 굵게 훑어서 그려 보는 편**이 낫습니다.
열 지점쯤 찍어 보면 봉우리가 하나인지 눈에 보이고, 하나라면 그 구간에서 삼분 탐색으로 정밀하게 좁히면 됩니다.

## 정리

크다 작다로 방향을 알 수 없는 문제에서도 반으로 자르는 발상은 살아 있습니다. 비교 대상을 바꾸면 됩니다.

- 값을 찾는 것이 아니라 **꼭짓점을 찾는 문제**입니다. 그래서 점 하나가 아니라 두 점을 견줍니다
- 삼등분 자리 두 곳을 비교하면 한 번에 삼분의 일이 사라집니다. 실수 범위에서는 반복 횟수를 고정합니다
- 기울기 부호로 보면 이분 탐색으로도 됩니다. 정수 구간이면 이쪽이 깔끔합니다
- **봉우리가 하나여야 합니다.** 모양을 모르면 굵게 훑어 그려 보고 시작하세요