16-01 탐욕 알고리즘

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

1.탐욕 알고리즘

 1)정의

- 최적의 값을 구해야 하는 상황에서 사용되는 방법으로 ‘현재에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘.

- 이때, 항상 최적의 값을 보장하는 것을 목표로 두지 않고 최적의 값에서 ‘근사한 값’을 목표로 한다.

 2)탐욕 알고리즘 과정

 

2.허프만 코딩

1)고정 및 가변 길이 코드

 -고정 길이 코드는 코드의 길이가 똑같은 값을 갖는 코드 체계 아스키 코드가 대표적.

 -가변 길이 코드는 코드의 길이가 다른 값을 가지는 코드 저장 공간을 절약을 위해서 사용된다.

2)접두어 코드(Prefix Code)

 -접두어란 다른 낱말 앞에 위치해서 새로운 낱말을 만드는 단어이다.

 -접두어 코드는 가변 길이 코드 중 하나로서 코드 집합에서 어느 코드도 다른 코드의 접두어가 되지 않는다.

 -예를 들어 {"0","1","01","010"}의 코드집합에서 "0",과"01"은 다른 코드 "010"의 에서 접두어가 되므로

  접두어 코드가 될 수 없다.

 -{"00"."010","100","101"}의 코드 집합에서 어느 코드도 다른 코드의 접두어가 되지 않는다.

 -위의 각 접두어 코드들을 각각 a,b,c,d로 정의한다면  'abcd' 는 00010100101로 표현할 수 있다

3)허프만 코딩

 - 텍스트 압축에 주로 쓰이는 알고리즘, 원본 데이터에서 자주 출현하는 문자는 적은 비트의 코드로 변환하여 표현하고 출현 빈도가 낮은 문자는 많은 비트의 코드로 변환하여 표현함으로써 전체 데이터를 표현하는데 필요한 비트 수를 줄이는 방식.

3.허프만 트리

1)정의

 -허프만 트리는 접두어 코드를 표현하는 이진 트리.

 -트리의 높이의 값이 접두어 코드의 자릿수가 되고 부모노드의 입장에서 트리의 왼쪽일 경우 0,

  오른쪽일 경우 1로 표현된다.

 -접두사 코드는 모두 잎 노드로 표현되어야 한다.

 -노드에는 그 접두사 코드가 가리키는 문자가 있다.

자가 있다.

2)작성과정

 

2)데이터 압축

-접두사 코드모음 {"0"."11","100","101"}에서 적은 양의 비트를 가진 접두사 코드를  많은 빈도 수를 가진 글자에 부여한다.

-원본 문자열 'aaabaacdd'를 압축한다 하였을 때

-'000100001011111'같이 변환이 된다. 원본 문자열이 아스키 코드로 (총 72비트)로 되었다고 했을 시

  15개의 0,1로 이루어진 15비트 수로 압축 되었다.

3)데이터 압축 해제