Algorithm 9 - Greedy Approach & Huffman Code

Greedy Algorithm
Dynamic programming은 subproblem을 모두 해결하여 최적의 결과를 도출해낸다. 그러나 모든 subproblem을 해결하는 것은 optimization problem에서 필요하지 않은 경우도 많다. (unnecessary - overkill) 이를 해결하는 방법이 greedy approach이다. 지금 현재의 상태를 보고, 가장 최적인 선택을 내리는 것이 이 방법이다. locally optimal choice를 내리고, 이 선택들이 global optimal로 이어지기를 바라는 것이다. 반드시 이런 최적 결과를 낼 수 있는 것은 아니지만, 대부분의 최적화 문제는 이 방법으로 해결가능하다. 따라서 subproblem을 풀기 전에 choice를 먼저 내린다는 점이 DP랑 가장 큰 차이점이다.

activity selection problem : 빈 강의실에 강의들을 겹치지 않게 배정하는 문제 형식. 각 강의의 길이가 겹치지 않으면서 가장 많은 강의를 배정해야 한다. 앞서 여러 문제들을 해결한 것 처럼 dynamic programming을 이용하여 이를 해결할 수도 있지만 이것이 이 문제를 해결하는 최적의 방법은 아니다. 이를 이용하려면 table의 모든 경우의 수를 다 고려하기 때문에 필요 없는 것들까지 계산하게 되기 때문이다. (O(n3)의 지나치게 큰 time complexity를 가진다)

이를 해결하는 것이 Greedy algorithm을 이용한 approach이다. 가장 빠른 finish time을 가지는 강의를 하나씩 선택하면, 가장 많은 강의를 선택하여 배정할 수 있다. 주어진 상황에서 가장 이득인 선택을 내리는 것이다. 그리고 이 문제에 대해서는 greedy approach로 optimal solution을 얻을 수 있다. (왜냐하면 가장 빨리 끝나는 finish time을 가지는 강의는 어떤 optimal solution에는 포함되어 있을 것이기 때문)

이 방법은 time complexity가 O(n)으로 줄어든다. 단, activity들이 finish time의 order에 따라 sort 되어 있지 않다면 O(nlogn)이 필요하다.

greedy algorithm을 사용할 때는 어떤 subproblem에서 greedy choice을 선택했을 때 각 step의 subproblem이 하나로 줄어들고, 해당 상황에서 내린 greedy choice가 optimal solution에 포함된다는 보장이 있어야 한다. 이를 정리하면 아래와 같이 두 가지 key ingredient로 표현할 수 있다.
- Greedy-choice property : local optimal choice를 결합하여 global optimal solution으로 도달할 수 있어야 한다.
- Optimal substructure : dynamic programming에서와 동일하게, subproblem에서 optimal solution을 내리고 이들을 결합하면, 전체 문제에서도 optimal solution을 얻을 수 있어야 한다는 것이다.

Greedy approach는 subproblem이 해결되기 전에 이들을 고려하지 않고 가장 좋아보이는 것을 선택한다. 따라서 매 스텝마다 하나의 subproblem만 생성되므로 implement 하는데 훨씬 빠르고 간단하다. 그리고 subproblem에 대한 solution을 재사용하지 않는다.
DP는 subproblem이 해결된 뒤에 선택을 하므로 전체 subproblem을 해결해야 최적의 선택을 내릴 수 있다. 그리고 매 단계마다 여러 개의 subproblem이 형성될 수 있기 때문에 구현하기 복잡하고 느리다. 그러나 subproblem에 대한 solution을 reuse 하기 때문에 효율적이고, global optimal에 반드시 도달할 수 있다.

따라서 문제에 따라 적절한 것을 선택하여 사용할 수 있어야 한다. 일반적으로 간단한 문제는 DP보다는 greedy를 사용하면 더 쉽게 해결할 수 있다.


Huffman Code
greedy approach based data compression method : 20~90 %의 data용량을 줄이는데 사용.
컴퓨터 구조에서 배운 것 처럼 데이터를 binary character code로 encode/decode 할 수 있다.
예를 들어 a =00, b =01 ... 과 같이 데이터를 코드로 치환할 수 있다.

- Fixed length code : 각 문자에 모두 동일한 크기의 코드를 할당. 이 경우, 종류가 늘어날 수록 전체 코드의 길이도 같이 늘어나므로 비효율적이다.
- Variable length code : 상기한 문제를 없애기 위해 frequency가 높은 것은 짧은 코드 길이로, 상대적으로 잘 나오지 않는 것에 긴 코드를 할당하면 전체 코드가 차지하는 용량을 줄일 수 있다. 이를 가장 효율적으로 구성하는 방법이 huffman code이다.

이 때 필요한 전체 메모리 공간은 각 캐릭터의 frequency * required memory space의 합으로 구할 수 있다.

Prefix code
서로 다른 길이의 코드들이 연결되어 있을 때 각 문자를 구별하기가 어려울 수 있다. 따라서 이 ambiguous problem을 해결할 방법이 필요하다. 예를 들어 a가 0, b가 1, C가 01이라면 001이 aab인지, ac인지 알 수 없다. 따라서 각 문자를 나타내는 codeword가 다른 codeword의 prefix가 되지 않도록 해야 한다. 이를 prefix-free code라 한다.

binary tree로 codeword를 나타낼 수 있다. fixed length라면 모두 같은 높이를 가지는 CBT로 나타내어 root 부터 leaf node까지 선택한 가지를 코드로 선택할 수 있다. variable length 라면 각 코드의 길이에 따라 서로 다른 높이의 leaf node가 존재하도록 하여 full binary tree를 만들어 나타낼 수 있다. 이전과 마찬가지로 root에서 경로를 선택하면 각 leaf node character에 해당하는 codeword를 얻을 수 있다. 이 때 prefix-free가 될 수 있도록 가지를 선택해야 한다.

종합하면, full binary tree로 나타낸 prefix-free code는 가장 frequency가 높은 것 부터 root에 가까운 leaf node가 되도록 하여 최적화된 codeword를 형성할 수 있다.
그리고 huffman code로 해당 FBT를 만들어낼 수 있다.

Constructing Huffman code
C개의 character가 있을 경우, FBT는 c개의 leaf node를 가지고, c-1개의 internal node를 가져야 한다. 그리고 이를 least frequency를 가지는 두 character를 선택해가며 tree를 bottom부터 구성하면 greedy algorithm을 적용할 수 있다. 이 때 각 character의 frequency를 internal node의 값으로 설정하면, 낮은 것들부터 쉽게 처리할 수 있다.

이는 binary tree를 사용한 heap sorting과 동일한 O(nlogn)의 time complexity를 가진다. (왜냐하면 min heap을 만드는데 O(n), Merge / min-heapify가 O(logn)을 가지고 n-1번 반복됨. 그리고 이 둘의 합.)
Proof of Huffman code
이 방법을 사용해 찾아낸 codeword가 최적이라는 것을 증명하려면 지난시간에 배운 것 처럼 해당 문제가 greedy algorithm으로 해결가능하다는 두 조건을 증명해야 한다.

- lemma 1 : greedy choice property(optimal을 만들 때 greedy한 선택이 포함됨) 이는 a,b / x,y를 이용해 optimal tree의 leaf node들의 위치를 바꾸어도 최적이라는 것을 통해 증명할 수 있다. (결국 자주 사용되는 것이 반드시 위쪽에 있어야 효율적이라는 것은 자명하므로, 가장 길이가 긴 것부터 bottom에 가도록 하는 greedy approach는 optimal을 만드는데 필수적이다.)
- lemma 2 : optimal substructure (subproblem의 optimal로 전체의 optimal 생성) 이미 형성된 optimal tree의 leaf 두 개를 하나로 생각하여 다른 tree를 만들어도, 전체 character set에 대해 optimal tree를 얻으려면 해당 leaf를 다시 두 개로 나누어야 한다는 것을 알 수 있다. 따라서 전체 tree를 형성하는 과정은 각 sub problem의 optimal로 구성할 수 있다.