꼭짓점은 양 끝이 아니라 두 점을 비교해서 찾는다

투사체를 던지는 각도를 정합니다. 각도를 올리면 사거리가 늘다가 어느 지점을 넘으면 다시 줄어듭니다. 가장 멀리 날아가는 각도를 찾고 싶습니다.

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

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

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

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

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

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 를 두 번 부르는 것이 비용입니다. 계산이 무거우면 이전 회차의 값을 하나 재활용하는 변형도 있습니다.

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

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

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

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

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

정수 구간에서 생기는 함정

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

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

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;

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

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

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

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

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

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

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

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

정리

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

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