코딩테스트 - 패스트캠퍼스 챌린지 21일차

수강한 강의
Chapter 20 그래프 고급 탐색 알고리즘
- 프림 알고리즘 3, 4

학습 후기
이전 강의에 이어 이번에도 프림 알고리즘 강의지만 전보다 향상된 프림 알고리즘이다. 원래는 20일 차에서 기본 프림 알고리즘과 개선된 프림 알고리즘을 동시에 올릴까도 생각했지만 생각보다 이해하는데 시간이 걸려서 오늘 개선된 프림 알고리즘에 대해 적어본다.

개선된 프림 알고리즘
간선이 아닌 정점을 중심으로 우선순위 큐를 적용하여 계산하는 알고리즘으로 다익스트라 알고리즘 구현한 방식과 비슷하다고 볼 수 있다.
다익스트라 알고리즘에서 처음 정점의 가중치 값을 0 나머지 정점까지 가는 길의 가중치를 무한대로 놓고 처음 정점과 이어진 정점의 가중치를 따라가며 저장된 정점까지의 가중치 값을 업데이트했듯이 개선된 프림 알고리즘에서도 초기 정점에 해당하는 key값은 0 나머지 정점에 해당하는 key값은 무한대로 놓고 시작한다. 정점에 인접한 정점들에 대한 가중치와 저장된 정점의 key을 비교하여 적으면 저장된 key 값을 업데이트한다.

개선된 프림 알고리즘 구현 시 고려사항
우선순위 큐 구조에서 이미 들어가 있는 데이터 값 변경 시, 최솟값을 가지는 데이터를 루트 노드로 올려 재구성하는 기능이 필요함.

시간 복잡도
개선된 프림 알고리즘의 시간 복잡도는 O(E log V)로 기존의 프림 알고리즘이 O(E log E)의 시간 복잡도를 가지는데 그래프에서 E(dge) > V(ertex) 이므로 (최대 V^2 = E 가 될 수 있음) 기존 프림 알고리즘보다 개선된 프림 알고리즘의 시간 복잡도가 개선되었다고 볼 수 있다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

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