[Algorithm] 탐욕 알고리즘(Greedy Alogrithm)

탐욕 알고리즘이란?

 

 최적해 문제에서 사용되는 알고리즘으로, 매순간 가장 최적으로 여겨지는 선택을 해나가며 최종적으로 최적의 해를 구하는 알고리즘이다. 동적 프로그래밍의 수행 시간문제를 보완하기 위해 고안된 알고리즘이다. 현재 동적 프로그래밍과 서로 보완해나가며 같이 사용되고 있다. 

 매 순간 최적을 고른다고 해서 이 것이 항상 최적인 해를 얻는다는 보장이 없으므로, 최적인 해답을 얻는지 확인하는 절차가 반드시 필요하다. 또한 모든 문제에서 탐욕 알고리즘이 적용가능한 것은 아니다.

 

 

허프만 코드(Huffman Code)

 

 탐욕 알고리즘의 대표적인 예로는 허프만 코드가 있다. 허프만 코드는 데이터 압축 방법으로, 문자의 출현 빈도수에 따라 서로 다른 길이의 코드를 부여한다. 일반적으로 빈도수가 높은 문자가 짧은 길이의 코드를 부여하여 데이터를 압축한다.

 

 어떤 텍스트의 문자 출현 빈도수를 검사하였는 데, 아래와 같은 결과가 나왔다고 가정하자.

문자	A	B	I	M	S	X	Z
빈도수	12	7	18	10	9	5	2

이때, 빈도수의 합이 가장 낮은 문자 2개를 묶어 하나의 트리를 생성한다. 트리의 루트에서는 빈도수의 합을 저장한다.

 이후 트리의 루트에 저장된 빈도수의 합, 각 문자의 빈도수를 비교하여 합이 가장 낮은 조합을 찾아 트리를 생성한다. 이 과정은 하나의 트리만 남을 때까지 반복한다. 

 완성된 트리 노드의 왼쪽 간선에는 0, 오른쪽 간선에는 1의 가중치를 부여한다.

 루트에서 부터 각 문자들을 탐색했을때 지난 간선들이 가중치 합이 허프만 코드가 된다. 완성된 허프만 코드는 아래와 같다.

문자	A	B	I	M	S	X	Z
코드	010	110	00	10	011	1110	1111

 완성된 허프만 코드를 각 문자에 치환함으로써 데이터를 압축한다.

 

 허프만 코드는 매 순간 가장 최적인, 합이 가장 작은 2개의 원소를 선택한다. 때문에 허프만 코드는 탐욕 알고리즘이며, 탐욕 알고리즘에서의 매 순간 가장 최적인 조건은 문제마다 다르다.