이 페이지는 "왜 ⌈log₂N⌉번이 한계인가"를 정보이론의 바닥까지 따라 내려간다. 결정트리의 평균 깊이가 Shannon 엔트로피 H(p) 아래로 내려갈 수 없다는 사실을 Kraft 부등식으로 증명하고, 매 질문의 50:50 분할이 왜 그 하한에 닿는지, 가변비용이면 왜 Huffman이 정확한 최적트리인지를 구현 수준의 C++ 코드로 라인 단위 해부한다.
"어디있니"는 스무고개다. 정답이 N개 후보 중 어느 하나인데, 매 질문은 후보 공간을 두(또는 여러) 부분집합으로 가르고 그 답을 듣는다. 점수는 "정답을 특정하기까지 던진 질문 수"이고, 우리는 그 기댓값을 최소화하려 한다.
이 문제의 핵심은 풀이가 아니라 하한에 있다. 어떤 영리한 전략을 써도 평균 질문 수가 절대 그 아래로 내려갈 수 없는 벽이 존재하며, 그 벽이 바로 후보 분포의 Shannon 엔트로피 H(p)다. 베스트 해법은 그 벽에 닿는 트리를 만드는 것이고, 두 갈래로 갈린다.
핵심 통찰은 두 경우가 같은 양을 최적화한다는 것이다 — 트리의 잎(후보)들의 가중 평균 깊이. 균등비용에서는 그리디가 그 최적에 닿고, 가변비용에서는 Huffman이 닿는다. 어느 쪽이든 결과는 H(p)라는 정보이론적 바닥에 의해 위에서 눌린다.
스무고개의 한 질문은 물리학의 한 측정과 같다. 측정 전 후보 공간의 불확실성이 H_before비트, 측정 후가 H_after비트라면, 그 질문이 제거한 불확실성은 IG = H_before − H_after다. 0/1 답을 주는 질문이 줄 수 있는 정보의 상한은 1비트이며, 그 상한은 답이 "예"·"아니오"일 확률이 정확히 0.5·0.5일 때만 달성된다. 따라서 "가장 좋은 질문"은 곧 "후보를 가장 균등하게 가르는 질문"이다.
이 절의 목표는 단 하나의 부등식 E[d] ≥ H(p)를 증명하는 것이다. 이것이 증명되면 "더 잘할 수 없다"가 수학적 사실이 되고, 베스트 해법은 "이 하한에 닿는 트리"로 완전히 규정된다.
이진 결정트리에서 각 후보 i는 정확히 하나의 잎에 놓이고, 루트에서 그 잎까지의 "예/아니오" 경로는 길이 ℓᵢ인 이진 문자열이다. 어떤 후보의 경로도 다른 후보 경로의 접두사가 될 수 없다(잎은 서로의 조상이 아니므로).
따라서 결정트리는 접두부호(prefix code)와 일대일 대응한다. 후보 i를 특정하는 데 드는 질문 수 ℓᵢ = 그 후보 부호의 길이. 평균 질문 수 E[d] = Σᵢ pᵢ ℓᵢ = 평균 부호 길이. 이 대응이 정보이론의 부호화 정리를 그대로 끌어쓸 수 있게 한다.
어떤 이진 접두부호의 부호 길이 ℓ₁,…,ℓ_N이든 Σᵢ 2^(−ℓᵢ) ≤ 1을 만족한다.
증명: 깊이 L = max ℓᵢ인 완전 이진트리를 생각하라. 잎이 2ᴸ개다. 깊이 ℓᵢ의 부호 단어는 그 아래 2^(L−ℓᵢ)개의 깊이-L 잎을 "독점"한다. 접두 조건상 이 잎 집합들은 서로 겹치지 않으므로 Σᵢ 2^(L−ℓᵢ) ≤ 2ᴸ. 양변을 2ᴸ로 나누면 부등식이 나온다.
후보 i가 정답일 확률이 pᵢ일 때, 어떤 이진 결정트리든 평균 질문 수 E[d] = Σ pᵢ ℓᵢ는 후보 분포의 Shannon 엔트로피 H(p) = −Σ pᵢ log₂ pᵢ 이상이다.
qᵢ = 2^(−ℓᵢ) / C로 정의하자. 여기서 C = Σ 2^(−ℓᵢ) ≤ 1(Kraft Lemma). 그러면 qᵢ는 합이 1인 확률분포다.
차이를 직접 계산한다:
E[d] − H(p) = Σ pᵢ ℓᵢ + Σ pᵢ log₂ pᵢ = Σ pᵢ ( ℓᵢ + log₂ pᵢ )
ℓᵢ = −log₂(C·qᵢ) = −log₂ qᵢ − log₂ C를 대입하면:
E[d] − H(p) = Σ pᵢ ( log₂(pᵢ/qᵢ) − log₂ C ) = D(p‖q) − log₂ C
여기서 D(p‖q) = Σ pᵢ log₂(pᵢ/qᵢ)는 KL 발산으로 항상 ≥ 0(Gibbs 부등식)이다. 그리고 C ≤ 1이므로 −log₂ C ≥ 0. 두 비음수 항의 합이므로 E[d] − H(p) ≥ 0.
Theorem 1은 협상 불가능한 벽이다. 후보가 균일 분포(pᵢ = 1/N)면 H(p) = log₂N이고, 따라서 어떤 천재적 질문 전략도 평균 log₂N번 미만으로 끝낼 수 없다. N=10⁶이면 약 20번 — 스무고개라는 이름이 우연이 아니다.
매 질문이 현재 후보 집합을 확률질량 기준 정확히 50:50으로 가를 수 있다면, 그렇게 만든 트리의 평균 깊이는 정확히 H(p)다 — Theorem 1의 하한을 등호로 달성한다.
50:50 분할은 답의 엔트로피가 H(½,½)=1비트 — 한 질문이 정확히 1비트를 제거한다. 정보 획득 IG = H_before − H_after = 1.
후보 i의 잎에 도달하기까지 제거된 총 불확실성은 시작 엔트로피 전부를 그 후보 관점에서 본 양 −log₂ pᵢ다. 매 질문이 정확히 1비트를 제거하므로 깊이 ℓᵢ = −log₂ pᵢ. 그러면 E[d] = Σ pᵢ ℓᵢ = −Σ pᵢ log₂ pᵢ = H(p). 등호 달성.
주의: 후보 확률이 정확히 2의 거듭제곱이 아니면 완벽한 50:50 분할이 불가능해 ℓᵢ를 정수로 올림해야 하고, 이때 H(p) ≤ E[d] < H(p)+1 — 하한에서 최대 1만큼만 벗어난다(Shannon 부호화 정리).
구현은 두 모드다. 균등비용에서는 매 단계 정보 획득이 최대인 질문을 그리디로 고른다. 정보 획득은 분할 후 가중 엔트로피로 계산된다.
#include <vector>#include <cmath>#include <functional>using namespace std;// 후보 부분집합의 Shannon 엔트로피 (균일 분포 가정 시 log2 크기)double entropy(const vector<double>& p) { double sum = 0, H = 0; for (double x : p) sum += x; if (sum <= 0) return 0; for (double x : p) { if (x <= 0) continue; double q = x / sum; H -= q * log2(q); // −Σ q·log2(q) } return H;}// 질문 q가 후보 집합을 가를 때의 정보 획득// answers[i] = 후보 i에 대한 질문 q의 답 (0=no, 1=yes)double infoGain(const vector<double>& w, const vector<int>& answers) { vector<double> yes, no; for (size_t i = 0; i < w.size(); ++i) (answers[i] ? yes : no).push_back(w[i]); if (yes.empty() || no.empty()) return -1; // 0-split은 무의미 double total = 0, sy = 0; for (double x : w) total += x; for (double x : yes) sy += x; double wy = sy / total, wn = 1.0 - wy; return entropy(w) - (wy * entropy(yes) + wn * entropy(no));}// 평균 질문 수를 최소화하는 결정트리를 재귀적으로 구성double buildTree(vector<int> cand, // 남은 후보 인덱스 const vector<double>& prob, // 후보별 확률 const vector<vector<int>>& Q) { // Q[q][i] = 답 if (cand.size() <= 1) return 0; // 후보 1개 → 질문 불필요 vector<double> w; for (int c : cand) w.push_back(prob[c]); int bestQ = -1; double bestIG = -1; for (size_t q = 0; q < Q.size(); ++q) { vector<int> ans; for (int c : cand) ans.push_back(Q[q][c]); double ig = infoGain(w, ans); // 50:50에 가까울수록 큼 if (ig > bestIG) { bestIG = ig; bestQ = q; } } vector<int> yes, no; for (int c : cand) (Q[bestQ][c] ? yes : no).push_back(c); double total = 0, sy = 0; for (int c : cand) total += prob[c]; for (int c : yes) sy += prob[c]; double wy = sy / total, wn = 1.0 - wy; // 기대 질문 수 = 1(이번 질문) + 가중 자식 비용 return 1.0 + wy * buildTree(yes, prob, Q) + wn * buildTree(no, prob, Q);}
infoGain이 0-split(yes나 no가 빈 경우)에 −1을 반환하는 데 주목하라. 한쪽으로 모두 몰리는 질문은 후보를 전혀 가르지 못해 정보 획득이 0 — 그런 질문을 고르면 트리가 영영 끝나지 않는다. −1 반환으로 argmax에서 자동 배제된다. 그리고 entropy는 입력 가중치 합으로 정규화(x/sum)하므로, 후보 부분집합에 그대로 적용해도 올바른 조건부 엔트로피를 준다.
그리디 엔트로피 분할은 모든 질문 비용이 같을 때만 최적이다. 질문마다 비용이 다르거나, "정답 후보의 부호 길이"를 직접 최적화하려면 — 즉 후보별 확률 pᵢ가 주어지고 그것에 맞는 최소 기대길이 트리를 원하면 — Huffman이 정확한 답을 준다.
#include <queue>#include <vector>using namespace std;// 후보 확률 prob[]로 Huffman 트리를 만들고 기대 질문 수 반환double huffmanExpectedDepth(vector<double> prob) { if (prob.size() <= 1) return 0; // 최소 힙 — 가장 확률 낮은 둘을 먼저 합침 priority_queue<double, vector<double>, greater<>> pq; for (double p : prob) pq.push(p); double totalCost = 0; while (pq.size() > 1) { double a = pq.top(); pq.pop(); // 가장 작은 둘 double b = pq.top(); pq.pop(); totalCost += a + b; // 합쳐진 노드는 깊이 +1 — 합산 누적 pq.push(a + b); // 내부 노드를 다시 삽입 } return totalCost; // = Σ pᵢ·ℓᵢ = 기대 질문 수 (최소)}
엔트로피 그리디: 트리 깊이가 O(log N), 각 깊이에서 모든 질문 |Q|개를 평가하고 평가당 후보 스캔 O(N) — 전체 O(N·|Q|·log N). N=10⁶, |Q|가 수십이면 ~10⁸으로 -O2 한계 안.
Huffman: 최소 힙에 N개를 넣고 N−1번 "둘 빼고 하나 넣기"를 한다 — 각 힙 연산 O(log N)이므로 전체 O(N log N). N=10⁶이면 ~2×10⁷ — 즉시 끝난다.
매 단계 정보 획득을 최대화하는 그리디는 직관적으로 옳아 보인다. 그러나 그것이 전역 최적 트리를 준다는 보장은 일반적으로 없다. 정확한 조건을 따져보자.
모든 질문 비용이 1이고, 어떤 후보 부분집합도 정확히 절반으로 가르는 질문이 항상 존재한다면(가령 후보가 log₂N비트 ID로 라벨링되고 "ID의 k번째 비트는?"이 질문 풀에 있다면), 매 단계 50:50 분할이 가능하고 Theorem 2에 의해 그리디 트리의 평균 깊이가 H(p)=log₂N에 정확히 닿는다. 하한에 닿았으므로 그리디 = 전역 최적.
질문 A가 비용 1에 50:50을 가르고, 질문 B가 비용 10에 51:49를 가른다고 하자. 그리디는 정보 획득이 큰 A를 고른다 — 옳다. 그러나 질문 C가 비용 1에 90:10을, 질문 D가 비용 1에 50:50을 가르되 D 이후 남는 후보들에는 더 이상 좋은 질문이 없다면? 그리디는 한 단계만 보므로 D를 골라 정보 획득 1비트를 챙기지만, 전체 트리로 보면 C로 시작하는 편이 나을 수 있다. 그리디의 근시안이 드러나는 지점이다.
Huffman이 최적인 이유는 두 성질에서 나온다. (1) 최적 트리에서 가장 확률 낮은 두 후보는 형제다 — 아니라면 깊은 잎의 후보와 교환해 기대길이를 줄일 수 있어 최적성에 모순. (2) 그 두 후보를 합친 "합성 후보"로 줄인 문제의 최적해는, 원 문제의 최적해와 일대일 대응한다(합성 노드를 펼치면 원 트리, 기대길이 차이는 합쳐진 확률질량으로 일정).
(1)+(2)에서 "가장 작은 둘을 합치고 재귀"가 정확한 최적 트리를 만든다. 단, 이 논법은 비용이 깊이에 선형일 때만 성립한다 — 질문마다 비용이 다르면 "깊이 +1 = 비용 +1"이 깨져 교환 논법의 셈이 어긋난다. 그때는 Huffman 변형(가변비용 부호화, 예: Karp의 정수계획)이 필요하다.
| 전략 | 평균 질문 수 | 하한 대비 | 구현 | 평가 |
|---|---|---|---|---|
| 선형 탐색 — 한 명씩 확인 | N/2 | 지수적 초과 | 쉬움 | 정보 획득이 후보당 극소 — N이 크면 즉시 탈락 |
| 임의 이진 트리 | ~2 log₂N | ~2× | 쉬움 | 치우친 분할이 섞여 비트 효율 절반으로 낭비 |
| Shannon 하한 (참고선) | H(p) | 1.0× (정의) | — | 도달 불가능한 이론 바닥 — 실수 길이 가정 |
| 엔트로피 그리디 / Huffman | ⌈log₂N⌉ ≤ d < H(p)+1 | ≤ 1비트 초과 | 중간 | 균등비용 그리디 / 가변확률 Huffman — 하한에 밀착 |
표가 보여주는 것은 비트 효율의 스펙트럼이다. 선형 탐색은 질문 하나가 후보 한 명만 제거 — 정보 획득이 log₂(N/(N−1)) ≈ 0비트로 거의 0이다. 임의 이진 트리는 분할이 50:50에서 벗어날수록 1비트 미만을 챙겨, 평균적으로 하한의 약 2배가 든다. 엔트로피 전략만이 매 질문에서 1비트(또는 그에 가장 가까운 값)를 뽑아내 Theorem 1의 하한 H(p)에 1비트 이내로 밀착한다. 그리고 Theorem 1이 "그보다 더 잘하는 것은 불가능"임을 증명하므로, 엔트로피 전략은 증명 가능하게 최선이다.
argmax에서 거르지 않으면(코드의 −1 반환), 그런 질문이 무한히 선택되어 트리가 종료하지 않는다.
if (x <= 0) continue;로 명시적으로 건너뛰어야 한다.
x/sum)해야 한다. 전체 확률로 계산하면 자식 엔트로피가 과소평가되어 정보 획득이 부풀려진다.
이 풀이의 최적성 주장은 추측이 아니라 Theorem 1의 하한과의 비교다. 만든 트리의 측정 평균 깊이가 H(p)와 H(p)+1 사이에 들어오면, 그 트리는 정보이론적으로 더 개선할 수 없는 영역에 있다.
buildTree 또는 huffmanExpectedDepth가 반환한 기대 질문 수를, 같은 확률분포로 계산한 entropy(prob)와 비교한다. 균일 분포 N=16이면 H=4이고 트리 깊이도 정확히 4 — 문제 페이지의 시각화(16→8→4→2→1, "log₂16=4 정확")와 일치한다. 비균일 분포에서는 반환값이 항상 [H, H+1) 구간에 떨어지는지 확인하면 Shannon 부호화 정리의 경험적 검증이 된다.