최적화 문제에 사용되는 간단하고 직관적인 알고리즘이다. 전체 문제를 해결하기 위한 전체적인 최적의 방법을 찾으려고 할 때, 각 단계의 최적 선택을한다.
데이터 압축에 쓰이는 Huffman encoding 이나 최단 경로를 찾는 Dijkdstra’s algorithm에 성공적 이다.
Greedy Algorithm 구조
- 모든 선택의 합계
두가지 속성
- 각 단계에서 최적의 선택을 하여 글로벌 최적 솔루션에 도달
- 전체 문제에 대한 최적의 솔루션이 하위 문제에 대한 최적의 솔루션을 포함하는 경우
tip. greedy 알고리즘이 실패하는 문제에서는 dynamic programming이 더 나은 접근 방식일 수 있다.
다익스트라 알고리즘
graph에서 nodes간의 가장 짧은 거리를 찾는데 사용된다. 알고리즘은 방문하지 않은 노드들과 노드간의 거리가 계산된 셋을 유지한다. 알고리즘이 짧은 거리를 찾으면 짧은 경로를 반영한다. A->B로가는 가장 짧은 경로와 B->C로 가는 가장 짧은 경로는 A->C로 가는 가장 짧은 경로의 부분이 된다.
허프만 코딩
메세지 안에서 characters의 빈도를 기반으로 분석한다. 자주 사용되는 심볼이 많을 수 록 짧게 인코딩 된다.
허프만 코딩 알고리즘의 특징은 발생하는 특정 기호의 빈도 또는 확률에 대한 정보를 가져온다. 목록에서 가장 낮은 두개의 기호로 시작하여 아래에서 위로 접두사 트리를 만들기 시작한다. 이러한 기호를 가져와 이를 포함하는 하위 트리를 형성한 다음 목록에서 개별 기호를 제거한다. 다음으로 알고리즘은 목록을 검색하고 확률이 가장 낮은 두개의 기호 또는 하위 트리를 선택한다. 이를 사용하여 새 하위 트리를 만들고 목록에서 원래 하위 트리 기호를 제거한 다음 새 하위 트리와 조합된 확률을 목록에 추가한다. 모든 요소가 추가 될 때까지 반복한다.
출처