자연계열 Ⅲ번

[문제 3-1] 컴퓨터의 효율성을 지문에서 제시한 바와 같이 메모리의 크기에서 이해한다. 즉, 주어진 문자열이 컴퓨터에 저장될 때 차지하는 메모리의 크기를

메모리 크기 = 문자 수 * 문자에 배정된 비트 수

로 계산하여 메모리의 크기가 작을수록 컴퓨터의 효율성이 좋다고 이해하는 것이다. 방식 I 은 각 문자별로 동일한 2비트가 배정되어 있으므로

2비트 * 10개문자 = 20 비트

의 메모리를 차지하며, 방식 II는 각 문자별 발생빈도가 다르므로 각 문자에 배정된 비트수와 발생빈도의 곱, 즉

1비트 * 4회 + 2비트 * 3회 + 3비트 * 2회 + 3비트 * 1회 = 19 비트

의 메모리를 차지한다. 따라서 방식 II가 방식 I보다 효율성이 더 좋다.

[문제 3-2]

(1) 주어진 문자열의 문자 수는 [문제 3-1]과 같으나 각 문자의 발생빈도가 다르다. 방식 I의 경우는 문자별 발생빈도와 무관하게 2비트씩 배정되어 있으므로 총 20비트의 메모리를 차지한다. 그러나 방식 II의 경우, 문자별 발생빈도가 A는 1회, C는 2회, G는 3회, T는 4회이므로, 차지하는 메모리의 크기는

$\displaystyle 1*1+2*2+3*3+4*3=26$

비트로 방식 I 보다 효율성이 나쁘다.

(2) [문제 3-1]과 비교해 보면, 두 문자열의 문자수가 같음에도 불구하고 방식 II의 배정을 적용할 때, 효율성, 즉 메모리의 크기가 달라진다. 그 이유는 각 문자 A, C, G, T의 발생빈도가 달라졌기 때문이다. 각 문자의 발생빈도에 그 문자에 배정된 비트수를 곱하여 더한 것으로 총 비트수를 계산하기 때문이다. 따라서 한정된 문자들로만 구성된 자료를 처리할 경우, 발생빈도가 높은 문자는 짧은 비트로, 발생빈도가 낮은 문자는 긴 비트로 배정 하는 것이 컴퓨터의 효율성을 향상 시킬 것이다.