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)
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)
'공부 > 알고리즘' 카테고리의 다른 글
Elementary Graph Algorithms (0) | 2011.07.13 |
---|---|
Data Structures for Disjoint Sets (0) | 2011.07.11 |
Dynamic Programming (0) | 2011.07.09 |
11장 Hash Table (0) | 2011.07.08 |
8장 Sorting in Linear Time (0) | 2011.07.03 |