n개의 식별자 (a1, a2, …, an)로 구성된 이진탐색트리에 n … | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 10년 1회차
n개의 식별자 (a1, a2, …, an)로 구성된 이진탐색트리에 n + 1개의 외부 노드를 추가하여 확장 이진트리를 만들 수 있다. 각 ai의 탐색 확률이 pi이고, 각 외부 노드에 속하는 식별자, 즉 내부 노드에 있지 않은 식별자의 탐색 확률이 qi일 때 주어진 이진탐색트리 T의 전체비용은 다음 식과 같다.
cost(T)=∑1≤i≤npilevel(ai)+∑0≤i≤nqi(level(external node i)−1)\mathrm{cost}(T)=\sum_{1\le i\le n} p_i level(a_i)+\sum_{0\le i\le n} q_i(level(external\ node\ i)-1)
전체 비용이 최소인 이진탐색트리를 최적 이진탐색트리라 한다. 3개의 식별자가 (a1, a2, a3) = (do, if, while)이고, (p1, p2, p3) = (0.1, 0.2, 0.5), (q0, q1, q2, q3) = (0.05, 0.05, 0.05, 0.05)일 때, 최적 이진탐색트리는?
1
2
3
4
해설

최적 이진탐색트리는 while을 루트로 하고 왼쪽 자식 if, 그 왼쪽 자식 do로 이어지는 트리이며 비용은 1.65이다.

탐색 확률이 가장 큰 while(0.5)을 루트에 두어야 가중 레벨 합이 작아진다. 내부 노드 비용은 0.5×1+0.2×2+0.1×3=1.20.5\times1+0.2\times2+0.1\times3=1.2이다.

외부 노드의 (레벨-1) 합은 3+3+2+1=9이므로 0.05×9=0.450.05\times9=0.45, 전체 비용은 1.2+0.45=1.651.2+0.45=1.65이다.

  • do를 루트로 하고 오른쪽으로 if, while이 이어지는 트리: 2.0+0.45=2.452.0+0.45=2.45로 더 크다.
  • if를 루트로 하고 do와 while을 양쪽 자식으로 둔 균형 트리: 1.4+0.40=1.801.4+0.40=1.80으로 더 크다.
  • do를 루트로 하고 오른쪽 자식 while, 그 왼쪽 자식 if를 둔 트리: 1.7+0.45=2.151.7+0.45=2.15로 더 크다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 10년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기