알고리즘 설계 - 그리디

그리디 알고리즘은 현재 상태에서 가장 최적이라고 생각되는 결정을 계속해서 취하는 방식의 알고리즘이다. Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘은 모두 그리디 알고리즘에 속하며, 그래프에서 최적의 경로를 찾는 데 주로 사용된다.

1. **Prim 알고리즘 (Prim's Algorithm)**: Prim 알고리즘이란 주어진 그래프에서 최소 신장 트리를 찾는 알고리즘이다. 최소 신장 트리는 그래프의 모든 정점을 연결하는 간선들의 가중치 합이 최소인 트리를 말한다. Prim 알고리즘은 특정 정점에서 시작하여 가장 가중치가 낮은 간선을 선택하면서 트리를 확장해 나간다.

2. **Kruskal 알고리즘 (Kruskal's Algorithm)**: Kruskal 알고리즘도 Prim 알고리즘과 같이 최소 신장 트리를 찾는 알고리즘이다. 그러나 Kruskal 알고리즘은 간선을 가중치 순으로 정렬한 후, 가장 가중치가 작은 간선부터 선택하면서 트리를 구성한다. 선택 과정에서 사이클을 형성하는 간선은 제외한다.

3. **Dijkstra 알고리즘 (Dijkstra's Algorithm)**: Dijkstra 알고리즘이란 가중치가 부여된 그래프에서 최단 경로를 찾는 알고리즘이다. 주어진 출발점에서 다른 모든 정점으로의 최단 경로를 찾는다. Dijkstra 알고리즘은 출발점에서 가장 가까운 정점을 선택하면서 경로를 확장해 나간다.

이 세 알고리즘은 모두 그리디 알고리즘의 원칙을 따르지만, 사용되는 문제와 접근 방식에 차이가 있다. Prim 알고리즘과 Kruskal 알고리즘이 해결하는 문제는 최소 신장 트리를 찾는 것이고, Dijkstra 알고리즘이 해결하는 문제는 최단 경로를 찾는 것이다. Prim 알고리즘은 특정 정점에서 시작하는 반면, Kruskal 알고리즘과 Dijkstra 알고리즘은 모든 간선이나 정점을 고려한다는 차이점도 있다.