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

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

학습 후기
그래프 고급 탐색 알고리즘 강의의 난이도가 상당하다. 최단 경로 알고리즘의 이해, 최소 신장 트리, 크루스칼 알고리즘, 이번 강의의 프림 알고리즘까지 강의를 보면 좀 알 거 같은데 돌아서면 또 까먹는 거 같은 알고리즘들이다. 여러 번 강의를 반복해서 듣고 자바로 직접 구현해보며 완전히 이해할 때까지 익히는 게 중요한 것 같다.

프림 알고리즘
최소 신장 트리를 구하는 알고리즘 중 하나이며, 시작 정점을 정하고 시작 정점에 인접한 간선 중 최소 가중치를 가지는 간선으로 연결된 정점을 선택하고 다시 최소 가중치로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 구함

크루스칼 알고리즘과 프림 알고리즘 비교
공통점: 탐욕 알고리즘을 기초, 당장 눈앞의 최소 가중치를 선택해서 결과적으로 최적의 해를 찾음.
차이점: 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택하면서 최소 신장 트리를 구함
프림 알고리즘은 특정 정점을 먼저 선택한 후, 해당 점점에서 연결된 간선 중 가장 작은 가중치를 가진 간선을 선택, 간선으로 연결된 정점의 간선들 중 가중치가 가장 작은 간선을 선택하는 방식으로 최소 신장 트리를 구함.

프림 알고리즘 구현
프림 알고리즘을 구현하기 위해 간선에 해당하는 Edge클래스와 가중치가 가장 작은 간선을 뽑기 위해 우선순위 큐를 사용한다.
1. 모든 Edge 정보를 저장.
2. 임의의 정점을 선택, 연결된 정점 집합에 삽입
3. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입
4. 간선 리스트에서 최소 가중치를 가지는 간선부터 뽑으면서
1) 간선에 연결된 정점이 연결된 정점 집합에 있으면 continue, 사이클 생성 방지
2) 연결된 노드 집합에 없으면 해당 간선을 선택하고 간선 정보를 최소 신장 트리 리스트에 삽입
5. 선택된 간선은 간선 리스트에서 제거
6. 간선 리스트에 더 이상의 간선이 없을 때까지 4-5 반복

시간 복잡도
최악의 경우 O(E log E)의 시간 복잡도를 가짐

수강 인증샷

https://bit.ly/37BpXiC

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

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