그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘은 "현재 상황에서의 최적해를 선택하는 방식"이다. 백트래킹을 통해 추가적인 점검을 하지 않고, 현재 선택지 이외에는 검증을 하지 않는다. 하지만 그 해가 항상 최적해라는 보장을 할 수 없다는 한계가 존재한다. 위와 같은 최소 가중치 문제에서, 그리디 알고리즘을 적용하면 7과 10중에 7을 선택하고, 12와 15중에 12를 선택하여 7 + 12 = 19의 가중치를 해로 갖게 된다. 그러나 그림을 보면 알 수 있듯이 실제 최소 가중치는 10 -> 5를 선택하는 15이다. 그리디 알고리즘을 적용했을 때, 매 선택마다 부분 최적해는 구했지만, 전체 최적해를 구하지 못한 것이다. 따라서 그리디 알고리즘은 항상 최적해를 보장하지 못한다고 할 수 있다..