Greedy Algorithms

greedy algorithms은 그 상황에서 가장 최선의 선택을 한다. 그 선택이 optimal solution으로 되기를 바란다.
subproblems가 풀리기 전에 선택을 한다.
단지 하나의 subproblem만 생성된다.

Dynamic programming의 경우에는 subproblems를 푼 후에 선택을 한다는 점이 Greedy Algorithms 하고 비교된다.

Huffman Code
prefix code
Prefix가 없는 코드. 한 코드는 다른 코드의 prefix가 되면 안된다. 포함되면 안된다. 포함되면 해석할 때 여러개로 해석될 수 있다. 
코드로 트리를 만들었을 때 중간노드에 코드가 없고 leaf 노드에만 있으면 prefix code이다. 그리고 full binary tree(모든 노드가 자식이 둘)가 최적의 코드이다.

huffman code 만들기
min heap을 만들어서 빈도수가 작은 수 2개씩 뽑아 합쳐서 합친 수를 두개의 부모노드로 만들고 합친수를 힙에 넣어 다 합쳐서 한개만 남을 때까지 반복한다. 
min heap 만들기 O(n), n-1번 합치기. 작은 수 뽑을 때마다 min heapify O(lg n). 따라서 running time은 O(n lg n)