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

---

Part 2. 알고리즘 이론

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

10. 프림 알고리즘 (3)

---

• 프림 알고리즘: 대표적인 최소 신장트리의 알고리즘 중 하나. 당장 최소 비용을 선택하여 결과적으로 최적의 해를 찾는 탐욕 알고리즘을 바탕으로 함
• 시간 복잡도: 최악의 경우 O(ElogE) 시간복잡도를 가짐
• 개선된 프림 알고리즘: 간선이 아닌 노드를 중심으로 우선순위 큐를 적용. 다익스트라 알고리즘을 참고.
  cf. 다익스트라 알고리즘:  특정 노드를 기준으로 해당 노드에서 갈 수 있는 노드별 가중치를 구한 뒤, 연결된 노드 중 다음 노드로 이동하여 가중치를 비교하는 방식
• 개선된 프림 알고리즘의 시간복잡도: O(ElogV)

오늘은 개선된 프림 알고리즘을 배웠다. 프림 알고리즘의 경우 while문에서 모든 간선에 대해 계산할 수 있어서 O(ElogE)의 시간 복잡도를 갖는다. 간선(E)의 경우, 한 노드에서 여러 개의 간선이 생길 수 있으므로 최대 정점(V)^2가 될 수 있다. 그래서 프림 알고리즘을 개선할 필요성을 느꼈는지 O(ElogV)의 시간복잡도를 갖는 개선된 프림 알고리즘을 공부했다. 오늘은 간단하게 Path클래스와 Comparable 인터페이스를 구현한 Edge 클래스를 작성했다. 쥬피터 노트북으로 코드를 작성하고 있는데 오늘 배운 것만 실행해보니 아무것도 나오지 않는다. 그래서 전 수업에서 그래프 내용을 입력했던 코드를 실행했더니 갑자기 오류가 났다. 우리 좋았잖아 코드야.. 왜 갑자기 그런 거야…. 이 오류 때문에 후반부에는 강사님의 수업을 듣기만 했다. 내일 들을 수업은 오늘과 합치면 양이 너무 많아서 끊으셨다는데 두렵다... 화이팅..!

 

---

https://bit.ly/3FVdhDa

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

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