다음 문자와 빈도수에 대해 허프만(Huffman) 알고리즘을 이용하여 … | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 23년 1회차
다음 문자와 빈도수에 대해 허프만(Huffman) 알고리즘을 이용하여 트리를 구성했을 때, 빈칸 ㉠～㉣에 들어갈 문자는? (단, ○는 빈도수 노드, □는 문자 노드이다)
| 문자 | a | b | d | e | g | i | k |
|---|---|---|---|---|---|---|---|
| 빈도 수 | 50 | 4 | 2 | 8 | 1 | 25 | 6 |
1
a / i / b / k
2
a / i / k / b
3
i / e / d / g
4
i / e / k / b
해설
허프만 트리에서 ㉠은 i, ㉡은 e, ㉢은 k, ㉣은 b이다.
빈도가 가장 작은 두 노드를 반복해 합치면 g(1)+d(2)=3, 3+b(4)=7, k(6)+7=13, e(8)+13=21, 21+i(25)=46, 46+a(50)=96 순이다.
따라서 루트 오른쪽 문자 노드가 a, 그 아래로 ㉠ i, ㉡ e, ㉢ k가 차례로 붙고, 내부 노드 7의 오른쪽 ㉣이 b, 맨 아래 두 문자 노드가 g와 d이다.
- a·i·b·k 조합: a는 루트 바로 아래 문자 노드이고, b(4)는 k(6)보다 먼저 합쳐져 더 깊이 놓인다.
- a·i·k·b 조합: a는 루트 바로 아래 문자 노드이므로 ㉠ 자리는 i, ㉡ 자리는 e이다.
- i·e·d·g 조합: 가장 드문 g와 d는 맨 아래 두 문자 노드로 묶이고, ㉢·㉣은 k와 b이다.
오류나 개정된 내용이 보이면 알려주세요