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

원당이를 위해 이 문제를 어떻게 해결할지 고민해 주세요.

문제풀이)

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

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

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

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++,자료구조,알고리즘,이산수학 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://seunmi1981.tistory.com BlogIcon 구름 달빛 2021.07.29 13:54 신고

    포스팅 잘보고갑니다 더운여름 건강조심해요

  2. Favicon of https://kbh6628.tistory.com BlogIcon 청산사랑 2021.07.29 16:20 신고

    아이고 던디 어러븐 포스팅 잘보았습니다 ㅎㅎ
    수고하셨습니다

  3. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2021.07.29 16:29 신고

    허프만, 뭔가 복잡한 문제네요.
    잘 보고 갑니다.
    즐거운 하루 보내세요.

  4. Favicon of https://dragonphoto.tistory.com BlogIcon 드래곤포토 2021.07.29 16:58 신고

    쉽지 않네요
    즐거운 시간되세요

  5. Favicon of https://lsmpkt.tistory.com BlogIcon 가족바라기 2021.07.29 23:33 신고

    어렵지만 학생들은 잘 풀것ㅇ같아요

  6. Favicon of https://heysukim114.tistory.com BlogIcon *저녁노을* 2021.07.30 04:44 신고

    어렵네요.ㅎㅎ
    잘 보고갑니다.

  7. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2021.07.30 06:14 신고

    코딩으로 이렇게도 표현이 되는군요
    접하지 못한 저는 어렵습니다 ㅎ

  8. 핑구야날자 2021.07.30 07:30

    코딩을 하면 할수록 정말 재미 있는 분야가 아닐까 싶어요 사고력을 키우는데 상당한 도움이 되지요

  9. Favicon of https://paran2020.tistory.com BlogIcon H_A_N_S 2021.07.30 08:31 신고

    오늘 하루도 활기찬 하루 되세요ㅎ

  10. Favicon of http://deborah.tistory.com BlogIcon 데보라 2021.08.02 22:52

    알고리즘의 원리에 대해서 잠시 공부 해봅니다.

+ Recent posts