알고리즘 13 탐욕 알고리즘

탐욕 알고리즘 
- 최적해를 보장하지 않지만, 적정해를 빠르게 구해준다 
- 1. 부분 문제의 최적해를 구함 -> 부분해 집합에 추가 
- 2. 새로운 부분해 집합이 실행가능한지 확인 = 제약조건을 위반하는지 검사
- 3. 새로운 부분해 집합이 문제의 해인지 확인 -> 아직 완성 안됬을 경우 1번부터 반복


ex) 거스름돈 문제 
- 단위가 큰 돈으로만 거스름돈을 만듦 
- 손님에게 드려야 하는 액수 초과하는지 검사 
- 동전 총액이 일치하는 지 검사 

허프만 트리 
- 압축 알고리즘
- 접두어 코드 (노-프리픽스 코드) 
- 이진트리를 통해서, 나타낸다 ; 데이터 = 잎노드데이터 / 경로 = 접두어코드

- 사전 작업 ; 가장 빈도가 낮은 순서대로 저장
- 해 선택 ; 빈도가 가장 작은 노드 2개를 선택 
- 실행 가능성 검사 ; 데이터가 있는 노드가 모두 잎노드인지 검사 
- 해 검사 ; 모든 데이터가 잎노드에 들어있는 지 검사 

압축해제 방법
-> 압축 해제 버퍼를 준비 
-> 압축데이터를 앞에서부터 읽으면서 이진트리 경로를 조회 
-> 리프 노드 만날 경우 해당 데이터 읽어오기 

 

 

Algorithm/GreedAlgorithm at main · Sukmin-LanternK/Algorithm