1부터 20 사이의 숫자를 맞히는 데 최소 몇 번의 추측이 필요할까? 답은 이미 250년 전 수학자들이 증명해두었다. 5번이면 무조건 맞힐 수 있다. 운이 좋으면 1번, 아무리 재수 없어도 5번을 넘지 않는다. 그 마법의 이름이 이진 탐색이다.
이진 탐색이란
이진 탐색(binary search)은 정렬된 데이터에서 원하는 값을 찾을 때 매번 남은 범위를 절반씩 잘라내며 좁혀가는 방법이다. 컴퓨터 과학의 가장 기본적이고도 강력한 알고리즘 중 하나로, 구글 검색부터 데이터베이스 인덱스까지 안 쓰이는 곳이 없다.
업다운 게임에서 이진 탐색은 다음 규칙 하나로 요약된다.
왜 중간값이 최적인가
가능한 정답이 20개인 상황에서 10을 골랐다고 하자. 결과는 세 가지 중 하나다.
- 정답 = 10 (1/20 확률로 즉시 승리)
- 정답 > 10 (9/20 확률, 남은 후보 10개로 감소)
- 정답 < 10 (10/20 확률, 남은 후보 9개로 감소)
어떤 경우가 나오든 남은 후보는 최대 10개로 줄어든다. 만약 중간값 대신 3을 골랐다면? UP이 나올 확률이 훨씬 높고, 그때 남는 후보는 17개다. 별로 좁혀지지 않은 것이다.
수학적으로 이 성질을 정리하면 이렇다: N개의 후보 중에서 최적으로 추측하면 최대 log₂(N)번의 시도로 정답을 확정할 수 있다.
1부터 20까지, 실전 예시
정답이 14라고 가정하고 이진 탐색으로 접근해보자.
| 차례 | 범위 | 추측 | 결과 |
|---|---|---|---|
| 1 | 1~20 | 10 | UP (11~20으로 축소) |
| 2 | 11~20 | 15 | DOWN (11~14로 축소) |
| 3 | 11~14 | 12 | UP (13~14로 축소) |
| 4 | 13~14 | 13 | UP (14 확정) |
| 5 | 14~14 | 14 | 🎯 정답! |
운이 아주 좋으면 첫 시도에 맞을 수도 있지만, 최악의 경우에도 5번을 넘지 않는다. 이 성질이 바로 이진 탐색이 "필승법"이라 불리는 이유다.
범위별 최대 시도 횟수
범위가 커지면 시도 횟수가 폭발적으로 증가할 것 같지만, 로그 함수의 특성상 매우 느리게 늘어난다.
| 범위 | 최대 시도 횟수 | 후보 감소 방식 |
|---|---|---|
| 1~10 | 4번 | 10 → 5 → 3 → 2 → 1 |
| 1~20 | 5번 | 20 → 10 → 5 → 3 → 2 → 1 |
| 1~100 | 7번 | 100 → 50 → 25 → 13 → 7 → 4 → 2 → 1 |
| 1~1,000 | 10번 | 1,000 → 500 → 250 → ... |
| 1~1,000,000 | 20번 | 매번 절반씩 축소 |
백만 개의 후보에서도 20번이면 정답을 확정할 수 있다는 사실이 처음엔 믿기지 않는다. 이것이 알고리즘의 힘이다.
턴제 게임에서의 반전 — 필승법이 필승법이 아니게 되는 순간
업다운 게임에는 결정적인 반전이 있다. 혼자 맞히는 게임이 아니라, AI와 번갈아 맞히는 대결이다. 두 플레이어 모두 이진 탐색을 완벽히 알고 있다면 결과는 어떻게 될까?
답은 사실상 코인 토스가 된다. 두 플레이어 모두 최적 전략을 쓰면, 이기는 사람은 결국 "누가 먼저 추측하는가"와 "정답이 우연히 첫 몇 번의 추측 근처에 있는가"에 따라 결정된다. 이는 이론적 필승 전략이 대결 상황에서는 승률을 반반으로 만들 뿐이라는 흥미로운 결과다.
AI를 이기려면 심리를 써야 한다
완벽한 알고리즘이 반반 승부라면, 인간은 어떻게 이겨야 할까? 답은 두 가지다.
- AI가 실수하는 지점을 노려라. AI가 오차를 두고 추측하는 게임이라면, 인간이 이진 탐색을 정확히 따라가는 편이 통계적으로 유리하다.
- 운의 영역을 인정하라. 정답이 어디 있는지는 무작위이므로, 5판 중 2~3판을 지는 것은 실력이 아니라 자연스러운 확률이다. 5연승은 실력이 아니라 운에 가깝고, 반대로 5연패도 실력이 아니라 운이다.
업다운 같은 단순해 보이는 게임 속에도 이렇게 250년 넘은 수학과 최신 게임 이론이 숨어 있다. 다음에 게임을 할 때는 그냥 감으로 찍는 대신, 매번 중간값을 고르는 자신을 관찰해보시길. 몇 판 만에 승률이 눈에 띄게 오르는 것을 경험하게 된다.