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

concept

탐욕 알고리즘이란 매순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 최적해에 도달하는 기법을 가리킵니다. 탐욕 알고리즘이 잘 작동하는 문제는 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$가 다음과 같이 주어졌다고 칩시다(종료시간 기준으로 오름차순 정렬).

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

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

탐욕 알고리즘을 적용한 결과 한 교실에 배정할 수 있는 최대 수업의 조합은 $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비트가 필요할 겁니다.

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

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

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

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

허프만 코딩을 하려면 다음 그림과 같이 트리를 구축합니다. 우선 가장 빈도가 낮은 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})$입니다.