탐욕(Greedy) 알고리즘은 커다란 문제를 해결하기 위해 여러 단계를 나누어 해결하는 알고리즘의 하나입니다. 동적 알고리즘에서는 현 단계에서 다음 단계로 갈 수 있는 모든 경험을 수행하면서 문제를 해결하였습니다. 하지만 탐욕 알고리즘은 현 단계에서 갈 수 있는 다음 단계들 중에 최적이라고 판단하는 하나의 단계만 수행합니다. 따라서 현 단계에서 다음 단계로 갈 수 있는 모든 경험 중에 무엇을 선택할 것인지 결정하는 것이 중요합니다.
그런데 매 순간 최적이라고 판단하는 다음 단계를 선택하면서 전체 문제를 해결하였을 때 이 해결 방법이 전체 문제에 최적일 수도 있지만 최적이 아닐 수도 있습니다. 따라서 가치있는 탐욕 알고리즘은 매 순간 최적이라고 판단하면서 다음 단계로 진행하면서 문제를 해결하였을 때 전체 문제도 최적임을 증명할 수 있어야 합니다.
여기에서는 매 순간 최적의 선택을 하였을 때 전체 문제도 최적으로 해결할 수 있음을 증명한 몇 개의 알고리즘을 소개할게요. 첫 번째 알고리즘은 최소 개수의 거스름 돈을 계산하는 알고리즘이고 두 번째는 길이가 다른 노래를 테이프에 기록하고 맨 앞에서부터 원하는 노래를 찾고자 할 때 평균 탐색 비용을 최소로 하기 위해 기록하는 알고리즘입니다. 그리고 마지막으로 최소 신장 트리를 만들 때 사용하는 프림과 크루스칼 알고리즘입니다.