목록Greedy (1)

YYYEJI

[Algorithm] Greedy로 Huffman code 풀기

Greedy 란? 각 단계에서 가장 최적의 선택을 하는 것으로, 그 순간에는 최선의 선택이지만 전체적으로는 최적해를 보장하지는 않는 알고리즘입니다. Huffman code란? 데이터를 인코딩(encoding)/디코딩(decoding)하기 위해 필요한 알고리즘입니다. 인코딩하는 과정 ① 입력 문자열에서 문자의 빈도수를 구한다. ② 빈도수를 기준으로 이진 트리를 생성한다. ③ 왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1를 부여해서 huffman 코드를 생성한다. ④ 입력 문자열에서 찾은 huffman 코드를 순차적으로 연결하여 하나의 비트 스트림으로 생성한다. 디코딩하는 과정 ① 저장된 비트 스트림을 읽어 각 문자의 huffman code를 생성해서 원래 문자로 변형한다. 디코딩하는 과정에서 중요하게 살펴..
Algorithm 2023. 4. 18. 20:25
이전 Prev 1 Next 다음