아래 출처의 설명 들으면 다 이해될것임.
https://www.youtube.com/watch?v=haXz9MEOGbo
허프만 압축 이해해보기
HuffmanCoding
입력: 입력 파일의 n개의 문자에 대한 각각의 빈도수
출력: 허프만 트리
1 각 문자에 대해 노드를 만들고, 그 문자의 빈도수를 노드에 작성한다.
2 n개의 노드들의 빈도수에 대해 우선순위 큐 Q를 만든다.
3 while ( Q에 있는 노드 수 >= 2) {
4 빈도수가 가장 작은 2개의 노드(A와 B)를 Q에서 제거한다.
5 새 노드 N을 만들고, A와 B를 N의 자식 노드로 만든다.
6 N의 빈도수 <ㅡ A의 빈도수 + B의 빈도수
7 노드 N을 Q에 삽입한다.
}
8 return Q // 허프만 트리의 루트를 리턴하는 것이다.
복잡도 : O(nlogn)
'📈알고리즘 > 알고리즘' 카테고리의 다른 글
| 연속 행렬 곱셈 (0) | 2023.04.18 |
|---|---|
| 동적 계획 알고리즘(1)[플로이드 모든 쌍 최단 경로 알고리즘] (0) | 2023.04.13 |
| 그리디 알고리즘(6)[작업 스케줄링 JobScheduling] (0) | 2023.04.05 |
| 그리디 알고리즘(5)[집합 커버 문제 SetCover] (0) | 2023.04.05 |
| 그리디 알고리즘(4)[ 부분 배낭 문제(Fractional Knapsa) ] (0) | 2023.04.05 |