[컴퓨팅사고력] 간장 공장 공장장~ 문장 압축해 보기

원당이가 컴퓨터 시간에 수업을 듣는데 선생님이 다음과 같은 숙제를 내 주셨습니다. "간장 공장 공장장은 강 공장장이고 된장 공장 공장장은 공 공장장이다" 를 이진수를 이용해서 표현해 볼 수 있도록 나타내되 그 길이가 가장 짧게 표현을 해 보라고 하셨습니다. 원당이를 위해 이 문제를 어떻게 해결할지 고민해 주세요.

문제풀이)

이러한 문제는 허프만 코드라고 하는 압축 알고리즘을 사용하면 됩니다.

허프만 알고리즘의 특징은 발생빈도가 적은 문자를 많은 비트를 사용하고 발생빈도가 많은 문자를 적은 비트를 사용하게 되면 가장 최소의 비트로 어떤 텍스트 파일을 압축할 수 있는 알고리즘입니다.

먼저 허프만 알고리즘의 원리에 대해 알아 보겠습니다.

1) 발생 빈도가 가장 낮은 두 문자를 선택하여 하나의 이진 트리를 생성한다.

- 왼쪽 노드에 빈도 수가 낮은 문자, 오른쪽 노드에 빈도가 높은 문자를 위치시킨다.

- 빈도수가 같은 경우는 사전적으로 앞에 오는 문자를 왼쪽에 위치시킨다.

- 두 문자의 빈도의 합을 그 문자들의 부모노드로 한다.

2) 1)의 과정을 모든 문자가 하나의 이진트리로 묶일때 까지 반복한다.

3) 생성된 이진 트리의 왼쪽 노드에는 0, 오른쪽 노드에는 1을 부여한다.

4) 루트로부터 해당 문자까지의 0 또는 1을 순서대로 나열한다.

 

그렇다면 위의 알고리즘을 통해 선생님이 내 주신 문제를 풀어 보도록 하겠습니다.

먼저 문자가 나온 횟수를 세어 보면 위와 같습니다.

빈도가 가장 낮은 문자는 '간'과 '강' 입니다. (고,된,다 역시 가장 낮지만 빈도수가 같은 경우 사전적으로 앞에 오는 문자를 먼저 선택해 보았습니다.)

그 다음 빈도가 가장 낮은 문자 '고'와 '다'를 선택합니다.

그 다음 빈도가 낮은 '된' 과 "간,강" 을 선택합니다.

그 다음 빈도가 낮은 "고,다" 와 '은' 을 선택합니다.

그 다음 빈도가 낮은 "간,강,된" 과 '이' 를 선택합니다.

 

그 다음 빈도가 낮은 "간,강,된,이" 와 "고,다,은" 을 선택합니다.

그 다음 '공' 과 " " 를 선택한다.

그 다음 빈도수가 낮은 "간,강,된,이,고,다,은" 과 '장' 을 선택한다.

마지막 남은 두개를 선택해서 트리를 만들면 다음과 같습니다.

이렇게 만든 후에 왼쪽노드에는 0 오른쪽 노드에는 1을 부여합니다.

부여된번호를 이용하여 이진수를 만들어 보면 다음과 같이 만들수 있습니다.

처음 횟수를 나타내는 테이블을 비교해 보면 가장 많이 나오는 '장'은 2bit로 처리가 가능하고 적게 나오는 '간'은 6비트를 이용한다.

우리가 사용하는 압축 알고리즘의 원리가 위와 같은 형태로 되어 있으며 header 에는 어떤 글자가 어떻게 되어 있는지를 기록한 후 그 파일을 압축후에 압축 해제시에는 역으로 헤더를 이용하여 압축을 해제 하는 형식으로 프로그램이 되어 있다.

따라서 위의 테이블을 만들었으니 다음과 같이 이진수로 표현할 수 있다.

"간장 공장 공장장은 강 공장장이고 된장 공장 공장장은 공 공장장이다"

101110110001110001111110010010111100011111101010000001011011000111000111111001000100011111101010001

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

 

인천 서구 검단신도시 원당컴퓨터학원

 

 

원당컴퓨터학원에서는?

1. 4차 산업 시대의 흐름은 컴퓨터를 얼마나 이해하느냐에 따라 삶의 질이 틀려 질 수 있다는 것을 항상 염두에 두고 있습니다.

2. 알고리즘은 프로그래밍의 근원이 되는 문제해결 능력이며, 머신러닝은 IoT등에 의해 모여진 데이터를 활용하는 기법입니다.

3. 이에 따라 초,중,고 학생들이 알기 쉽게 이해하는 인공지능 부터 알고리즘까지 학생들의 실력에 맞춰 수업을 진행중에 있습니다.

4. 현재 초등학생이 고등학생이 되는 때에는 고교학점제 도입에 따라 자신이 전공하고자 하는 특기가 크게 부각 될것입니다.

5. IT 업체중 규모가 큰 곳에서는 코딩테스트(알고리즘테스트)로 블라인드 면접을 수행하는곳이 늘고 있습니다.

6. 미래 IT를 꿈꾸는 학생들의 산실이 되기 위해 항상 최선을 다하는 원당컴퓨터학원이 되겠습니다.

 

※ 정보영재 혹은 인공지능 관련 수업에 관해 궁금하신 분은 문의(032-565-5497) 주세요.

 

 

원당컴퓨터학원 커리큘럼

- OA : 학교 수행 평가에 꼭 필요한 컴퓨터 활용능력 향상

- IT 자격증 과정 : 취업대비,대학생인증제,승진을 위한 국가공인 자격증 취득과정

- 정보영재 : 정보올림피아드 및 알고리즘 대회/소프트웨어특기자전형/디미고 특별전형 대비/코딩테스트 대비를 위한 알고리즘 과정

- 프로젝트반 : 응용프로그래밍/웹프로그래밍/앱프로그래밍 등을 통해 직접 만들어 보면서 컴퓨터 프로그래밍 이해(소프트웨어 학생부종합전형/특성화고(디미고,선린고등) 특별전형대비)

- 인공지능 : 인공지능의 이해 및 실습을 통해 빅데이터 가공(4차 산업 시대의 축이 되는 인공지능 시대를 대비)

- 과고,영재고,컴퓨터학과(SW) 대학생을 위한 내신대비 : python,java,c++,자료구조,알고리즘,이산수학