패스트캠퍼스 캐시백 챌린지 07일
프림 알고리즘.
이번에도 중반부로 오게 된 이유,
알고리즘 과목 중간고사 범위 중 하나인 프림 알고리즘을 학습하기 위해서였다.
프림 알고리즘이란 무엇인가? 하니
특징을 나열하면 이러하다.
*프림 알고리즘은 MST(최소신장트리)를 구현하는 한 방법으로 다익스트라(Dijkstra) 알고리즘과 유사하게 동작한다.
(하지만 크루스칼에 더더욱 비슷해 보인다)
*프림 알고리즘을 대략적으로 설명하자면 보통 이렇게 하더라.
-각 정점들은인접한 정점 중 최소 비용으로 이동가능한 정점을 선택하여 추가한다.
-우선순위 큐를 이용하여 임의의 정점부터 인접한 정점을 거리를 기준으로 정렬한다.
-최소 거리의 정점을 꺼내서 다시 인접한 정점을 넣고 정렬한다.
-반복한다.
-???
-profit!
...... 하지만, 저건 sudoCode라고 하기에는 나같은 범재가 저것만으로 실제 구현을 하기 어렵다.
그래서 강의에서는
프림 알고리즘의 탐색방식을 더 친절하게 설명해 주었다.
1. 임의의 정점을 선택, '연결된 노드 집합'에 삽입
2. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입
3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서,
- 해당 간선에 연결된 인접 정점이 연결된 노드 집합에 이미 들어있으면, 스킵(cycle 발생 방지)
- 해당 간선이 연결된 인접 정점이 연결된 노드 집합에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입
4. 추출한 간선은 간선 리스트에서 제거
5. 간선 리스트에 더 이상의 간선이 없을 때까지 3~4번 반복
이 쯤 되니까, 이제야 좀 알아먹겠더라.
여기서도 마찬가지이다.
a) a라는 점에서 출발~
b) 인접한 비용이 4,8 두가지이니 가까운 b로 간다.
c) 인접한 비용이 8, 11, 8 세가지인데,
-해당 간선에 연결된 인접 정점이 연결된 노드 집합에 이미 들어있으면, 스킵
원칙에 따라서 동일한 비용이어도 c로 가야 한다.
d) 인접한 비용이 8,11,2,4,7이면 볼것도 없이 비용 2를 통해 i로 간다.
e) 여기도 판단에 고민할 거리가 없으므로 비용4를 통해 f로 간다.
f) 이게 좀 고민이다.
당장 근처만 해도 비용7이 2개에다 2가 있는데, 2는 딱봐도 cycle이 될것 같아서
아리까리 하다... 하지만 원칙 우선순위는 '최소' 이므로 비용 2짜리인 g로 가야 하는 것이다.
g) 다음으로도 마찬가지로 비용 1인 h로 연결한다.
h) 여기까지 와서야 대부분 돌았다. 남은 것은 왼쪽의 8,7,6이 있는데,
'이제는 다 cycle 조건에 걸리므로 처음부터 제외가능'하다.
그러므로 드디어 비용 7이어도 d점으로 갈 수 있는 것이다!!!
i) 그리고 마지막 남은 간선인 9짜리를 통해 목적지 e로 가게 되는 것이다.
이번 블로깅 퀄이 낮아보이는 것은,
강의내용 언급 방지를 위해 수정이 덕지덕지라 그런거니 이해바람.
그리고 내일부터는 실제 코딩도 내용에 붙이게 될 예정.
패스트캠퍼스 [직장인 실무교육]
프로그래밍, 영상편집, UX/UI, 마케팅, 데이터 분석, 엑셀강의, The RED, 국비지원, 기업교육, 서비스 제공.
fastcampus.co.kr
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.