크루스칼 알고리즘이나 프림 알고리즘 모두 이 탐욕 알고리즘에서 어떻게 컷을 선택할지, 어떻게 가중치가 작은 에지를 찾을지 구체화하는 과정에서 탄생했습니다. 다음 절에서는 먼저 크루스칼 알고리즘을 알아보겠습니다.
Tip 탐욕 알고리즘은 어디에 쓰나요?
탐욕 알고리즘은 그 구현이 쉽기 때문에 다양한 분야에서 쓰이고 있습니다. 알고리즘 대회의 단골 주제이기도 합니다. 다만 쓸 수 있는 경우가 한정되어 있다는 단점이 있습니다. 앞서 설명한 탐욕 특성을 모두 만족해야만 하지요.