허프만 코딩(Huffman coding) 알고리즘을 이용하여 다음 19… | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 16년 1회차
허프만 코딩(Huffman coding) 알고리즘을 이용하여 다음 19개 문자로 구성된 문자열을 압축하였다. 압축된 문자열에 사용된 비트 수는?
ababadcdabacdabcdde
1
39
2
42
3
44
4
46
해설

압축된 문자열은 42비트를 사용한다.

문자별 빈도는 a 6, d 5, b 4, c 3, e 1이다. 허프만 트리는 빈도가 가장 작은 두 노드를 반복해 합친다.

e(1) + c(3) → 4
4 + b(4) → 8
d(5) + a(6) → 11
8 + 11 → 19
코드 길이는 a·b·d 2비트, c·e 3비트이므로 6×2 + 5×2 + 4×2 + 3×3 + 1×3 = 42

  • 39는 42보다 짧은데, 허프만 코드는 접두어 코드 중 총 비트 수가 최소이므로 이보다 짧은 접두어 코드는 만들 수 없다.
  • 44는 42보다 길어 최적 코드인 허프만 코드의 결과가 될 수 없다.
  • 46도 42보다 길어 허프만 코드의 결과가 될 수 없다.

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

이어서 풀어보기

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