패스트캠퍼스 챌린지 19일차

---

Part 2. 알고리즘 이론

Ch 20. 그래프 고급 탐색 알고리즘

08. 프림 알고리즘 (1)

---

• 신장 트리 : 그래프의 한 종류로, 전체 노드/정점을 간선으로 연결하되 사이클이 형성되지 않은 트리
• 최소 신장 트리 : 그래프의 한 종류로, 전체 노드/정점을 간선으로 연결하되 사이클이 형성되지 않은 트리 + 간선의 가중치 합이 최소인 트리
• 프림 알고리즘: 대표적인 최소 신장트리의 알고리즘 중 하나. 당장 최소 비용을 선택하여 결과적으로 최적의 해를 찾는 탐욕 알고리즘을 바탕으로 함
• 크루스칼 알고리즘과 프림 알고리즘 비교: 두 알고리즘 모두 탐욕 알고리즘을 바탕으로 함. 크루스칼 알고리즘은 모든 노드/정점이 연결되어있고 그중 가중치가 낮은 간선부터 가중치가 높은 간선까지 선택하되, 사이클이 생기는 간선은 제외한다. 프림 알고리즘은 특정 노드를 기준으로 시작한다. 간선이 연결된 노드들의 간선 중 가중치가 낮은 간선을 연결하되, 크루스칼 알고리즘과 마찬가지로 사이클이 생기면 그 간선은 제외한다.
  
  

오늘은 프림 알고리즘에 대해 배웠다. 내가 요 며칠간 크루스칼 알고리즘이란 벽에 부딪히며 모르겠다 투정 부렸는데 공부를 허투루 한 건 아닌가 보다. 코드를 구현하는 건 또 다른 문제겠지만 일단 개념을 이해하는 게 어렵진 않았다. 이해했든 못했든 일단 꾸준하게 듣는 것이 가장 중요한 것 같다. 요즘 나의 후기를 보면 이중인격이 따로 없다. 이해가 가면 좋아하다가 이해가 안 가면 투정이란 투정 다 부리고....ㅎ 암튼 오늘은 프림 알고리즘의 개념만 배운 것도 아니고 이 알고리즘을 코드로 구현하는데 엣지 클래스와 그 외에 필요한 메소드도 함께 작성했으니까 크루스칼처럼 그렇게 어렵지는 않지 않을까…?

---

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

- 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.-