§ 1문제 정의
정답이 N개 후보 중 어떤 것인지 묻는 질문을 최소 횟수로 좁혀라. 각 질문은 후보 공간을 두(또는 여러) 부분집합으로 가른다. 어떤 질문을 골라야 가장 빨리 끝나는가?
이는 정확히 결정 트리(Decision Tree) 최적화이고, 정보이론적으로는 매 단계의 정보 획득량(Information Gain)을 최대화하는 문제다. Huffman 코딩과 같은 본질.
핵심 원리: 최적 질문은 후보 공간을 가능한 한 균등하게 양분한다. 50:50으로 가르는 질문이 정보이론적으로 1비트의 정보를 준다.
최적의 질문은 “예”와 “아니오”의 확률이 같은 질문이다 — 0.5와 0.5의 엔트로피가 1.0으로 최대다.
§ 2엔트로피 기반 결정 트리
16개 후보 → 매 단계 가장 균형잡힌 질문 선택. 4번 만에 후보 1개로 좁힘.
FIG. 20 — entropy-optimal binary decision tree
STEP 01 / 5
SPACE play/pause · ← → step · R reset
§ 3왜 엔트로피가 최적인가
결정 트리의 평균 깊이 하한은 정보이론의 핵심 결과 중 하나:
| 접근법 | 평균 질문 수 |
|---|---|
| 선형 탐색 (한 명씩) | N/2 |
| 임의 이진 트리 | ~2 log₂N |
| 엔트로피 최적 트리 | ⌈log₂N⌉ ≤ d ≤ ⌈log₂N⌉ + 1 |
| Shannon Lower Bound | H(p) (확률 분포) |
증명 스케치: 어떤 결정 트리 T의 평균 깊이 E[d] ≥ H(p) (Shannon). 매 노드에서 50:50 가까이 가르면 H의 한계에 가깝게 도달. 가변 비용 질문이면 Huffman 알고리즘으로 정확한 최적 트리.
정보는 비대칭에서 나온다. 한쪽으로 치우친 질문은 비트 효율이 떨어진다.
§ 4알고리즘 골격
solve(candidates, questions):
if len(candidates) == 1:
return candidates[0]
# 각 질문이 가르는 분할의 정보 획득 계산
bestQ, bestGain = None, -1
for q in questions:
yes = [c for c in candidates if q(c)]
no = [c for c in candidates if not q(c)]
if !yes || !no: continue # 0-split 무의미
p_yes = len(yes) / len(candidates)
p_no = 1 - p_yes
# 분할 후 평균 엔트로피
H_after = p_yes * H(yes) + p_no * H(no)
gain = H(candidates) - H_after
if gain > bestGain:
bestQ, bestGain = q, gain
# 가장 정보량 큰 질문 던지기
answer = ask(bestQ)
if answer == YES:
return solve(yes, questions - {bestQ})
else:
return solve(no, questions - {bestQ})
# 가변 비용일 경우: Huffman-like adjustment
# gain / cost ratio를 max