다음은 어떤 문자열에 포함된 문자들의 빈도수를 나타낸 표이다. 허프만(… | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 26년 1회차
다음은 어떤 문자열에 포함된 문자들의 빈도수를 나타낸 표이다. 허프만(Huffman) 코드를 적용하여 인코딩한 결과의 비트 수는?
| 문자 | a | b | c | d | e | f |
|---|---|---|---|---|---|---|
| 빈도수 | 7 | 20 | 10 | 5 | 50 | 6 |
1
98
2
202
3
300
4
331
해설
허프만 코드로 인코딩한 전체 비트 수는 202이다.
빈도가 가장 작은 두 노드를 반복해서 합친다.
5(d) + 6(f) = 11
7(a) + 10(c) = 17
11 + 17 = 28
20(b) + 28 = 48
48 + 50(e) = 98총 비트 수는 각 문자 빈도 × 코드 길이의 합이며, 이는 합쳐서 생긴 내부 노드 값의 합과 같다.
11 + 17 + 28 + 48 + 98 = 202
(검산: e 50×1 + b 20×2 + a·c·d·f (7+10+5+6)×4 = 50 + 40 + 112 = 202)
오류나 개정된 내용이 보이면 알려주세요