이번 글에서는 탐욕 알고리즘(Greedy Algorithm)을 살펴보도록 하겠습니다. 이 글은 경희대 한치근 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

Greedy Algorithm

탐욕 알고리즘이란 매순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 최적해에 도달하는 기법을 가리킵니다. 탐욕 알고리즘이 잘 작동하는 문제는 greedy choice property와 optimal substructure 두 가지 속성을 만족합니다. 전자의 경우 앞의 선택이 이후 선택에 영향을 주지 않는다는 걸 의미하고, 후자는 문제 전체에 대한 최적해(global optimum)가 부분문제에 대해서도 역시 최적해가 된다는 걸 뜻합니다.

예컨대 분할가능 배낭문제(Fractional knapsack problem)가 대표적인 탐욕 알고리즘의 사례에 속합니다. 배낭문제는 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제인데요. 분할가능 배낭문제는 짐을 쪼갤 수 있는 경우에 해당합니다.

분할가능 배낭문제는 단위 무게당 값어치가 가장 큰 짐을 먼저 넣으면 되는데요. 순간순간의 선택이 이후 선택에 영향을 주지 않고, 순간순간의 최적 선택이 전체 문제 최적해와 일치합니다. 따라서 분할가능 배낭문제는 탐욕 알고리즘으로 풀 수가 있습니다.

반면 짐을 쪼갤 수 없는 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라고 합니다. 짐을 쪼갤 수 없기 때문에 가능한 모든 조합에 대해 일일이 따져본 후에 가치의 합이 최대가 되도록 하는 조합을 찾는 문제가 되는데, 이 때는 동적계획법(dynamic programming)으로 문제를 풀게 됩니다. 다시 말해 모든 경우의 수를 따져보되 중간계산 결과를 저장해 두었다가 이를 다시 써먹는 방식으로 계산량 감소를 유도하는 전략입니다.

이 글에서는 탐욕 알고리즘의 대표 예시인 Activity-Selection Problem과 Huffman Coding에 대해 살펴보도록 하겠습니다.

Activity-Selection Problem

교실할당(classroom assignment)로도 불립니다. 한정된 교실 공간 내에서 최대 수업을 배정하는 문제입니다. 예컨대 9개 수업이 있고, 시작시간 $s$와 종료시간 $f$가 다음과 같이 주어졌다고 칩시다(종료시간 기준으로 오름차순 정렬).

$i$	1	2	3	4	5	6	7	8	9
$s_i$	1	2	4	1	5	8	9	11	13
$f_i$	3	5	7	8	9	10	11	14	16

종료시간이 가장 빠른 수업을 먼저 배치하게 되면 교실 가용시간은 항상 최대가 됩니다. 종료시간이 빠른 수업부터 차례로 배정하기 때문에 앞의 선택이 이후 선택에 변화를 주지 않고, 매순간 선택이 항상 최적이 됩니다. 이 문제는 탐욕 알고리즘 속성을 만족한다는 이야기이죠.

어쨌든 종료시간을 오름차순으로 정렬해 수업을 배정하면 다음과 같은 그림이 됩니다.

탐욕 알고리즘을 적용한 결과 한 교실에 배정할 수 있는 최대 수업의 조합은 $a_1, a_3, a_6, a_8$인 걸 확인할 수 있습니다. 물론 $a_2, a_5, a_7, a_8$ 또한 가능합니다만, $a_1$을 기본 결과값으로 포함시킨 앞의 결과보다 더 나은 해라고 할 수는 없습니다..

이 문제의 계산복잡성은 $O(n)$입니다. 첫번째 수업을 기본 결과값으로 포함시키고, 첫 수업과 나머지 $n-1$개 수업이 겹치는지 여부만 확인하면 되기 때문입니다.

Huffman Coding

허프만 코딩이란 탐욕 알고리즘을 사용해서 데이터를 압축하는 기법입니다. 기본 컨셉은 다음과 같습니다. 예컨대 우리가 가진 데이터는 네 가지 문자(A, B, C, D)만 있다고 칩시다. 정석대로 문자 인코딩을 하는 상황이라면 다음과 같이 글자 하나당 2비트가 필요할 겁니다.

Symbol	Code
A	00
B	01
C	10
D	11

그런데 데이터의 문자별 빈도는 각각 다음과 같다고 칩시다.

Symbol	Frequency
A	6
B	2
C	3
D	1

위의 경우 전체 데이터를 저장하는 데 총 24비트($6×2+2×2+3×2+1×2$)가 필요합니다. 이제 허프만 코딩을 적용해 빈도가 높은 문자는 적은 비트를 할당한다고 치겠습니다. 다음과 같습니다.

Symbol	Code
A	0
B	110
C	10
D	111

허프만 코딩 적용 결과 전체 데이터를 저장하는 데 총 21비트($6×1+2×3+3×2+1×3$)가 필요합니다. 기존보다 3비트를 줄이는 데 성공했습니다. 압축률은 데이터가 클 수록 좋아질 것입니다.

허프만 코딩 수행 과정은 다음과 같습니다. 예컨대 데이터의 문자별 빈도가 다음과 같다고 치겠습니다.

Symbol	Frequency
A	15
B	6
C	7
D	12
E	25
F	4
G	6
H	1
I	15

허프만 코딩을 하려면 다음 그림과 같이 트리를 구축합니다. 우선 가장 빈도가 낮은 H를 말단 왼쪽 노드로 선택합니다. 말단 오른쪽 노드엔 그 다음 적은 F를 놓습니다. 이 둘의 부모노드는 둘의 빈도를 합친 5가 됩니다.

이번엔 이 부모노드(5)를 포함해 가장 작은 값(5)을 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 B를 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 11이 됩니다.

이번엔 이 부모노드(11)를 포함해 가장 작은 값(G)을 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 C를 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 13이 됩니다.

이번엔 이 부모노드(13)을 포함해 가장 작은 값(11)를 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 D를 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 23이 됩니다.

이번엔 이 부모노드(23)을 포함해 가장 작은 값(I)를 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 23을 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 38이 됩니다.

이번엔 이 부모노드(38)을 포함해 가장 작은 값(E)을 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 28을 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 53이 됩니다.

이번엔 이 부모노드(53)을 포함해 가장 작은 값(38)을 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 53을 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 91이 됩니다.

문자 각각의 코딩 결과는 예컨대 다음과 같습니다. 빈도가 클 수록 그 길이가 짧은 걸 확인할 수 있습니다.

• H : 01000
• G : 1100
• E : 10

허프만 코딩의 계산복잡성은 $O(n\log{n})$입니다.