[C++] Data Structure & Algorithm/MST(Minimum Spanning Tree)4 [MST] Chapter 04. Prim 알고리즘을 이용한 맵 생성 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/9b505b2dbc9bb895add268c2114b1ba33fec4f3a Prim 알고리즘을 이용한 맵 생성 · developeSHG/Data_Structure-Algorithm@9b505b2 developeSHG committed Aug 17, 2023 github.com 크루스칼 알고리즘과 거의 유사하다. 다른 부분은 간선을 어떻게 수집할 것인지 순서가 달라진다. 크루스칼 알고리즘은 탐욕적인 방법을 이용했다. 작은 간선부터 탐색해서 사이클이 발생하지 않는 간선을 추가해줬다. 위처럼 그룹을 나누다가 경우에 따라 그룹을 병합했다. 프림 알고리즘은 하나의 시작점으로 구성된 트리에.. 2023. 8. 16. [MST] Chapter 03. Kruskal 알고리즘을 이용한 맵 생성 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ea4d99bf27f79da3e7b4f924d6e2ca50d9c63744 Kruskal 알고리즘을 이용한 맵 생성 · developeSHG/Data_Structure-Algorithm@ea4d99b developeSHG committed Aug 17, 2023 github.com 미로라면, 랜덤성이 보장이 되야하는데 코드 특성상 아래랑 우측이 일직선으로 뚫린 현상으로 맵이 만들어지게 했었다. 이 부분을 개선시키기 위해 Kruskal 알고리즘을 이용한 맵 생성을 해볼 것이다. Kruskal을 어떻게 응용할 지 생각해보면 BST를 만들 때, 어떻게 만들었는지를 생각해보자. 이전까지.. 2023. 8. 16. [MST] Chapter 02. Kruskal 알고리즘 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/e91776c4a5ed1f8b2a4cb1104ac89349e77c8bcf Kruskal · developeSHG/Data_Structure-Algorithm@e91776c developeSHG committed Aug 17, 2023 github.com 다시 복습하면 그래프는 [현실 세계의 사물이나 추상적인 개념간]의 [연결 관계]를 표현한다 했었다. 전형적인 그래프는 정점들과 정점들을 연결하는 간선으로 이루어진 것이 그래프였고, 예로 소셜 네트워크 관계도, 지하철 노선도를 그래프로 표현할 수 있었다. 위 사진처럼 정점에 대한 간선을 연결해서 모든 길을 뚫어놓은 상태이고, BF.. 2023. 8. 16. [MST] Chapter 01. Disjoint Set (Union-Find) GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/131723902448c69701b98d17c20188b35e06dbc0 Disjoint Set · developeSHG/Data_Structure-Algorithm@1317239 developeSHG committed Aug 14, 2023 github.com Minimum Spanning Tree => 그래프/트리의 활용정도가 된다. 최소 스패닝 트리 (Minimum Spanning Tree)을 알기 전에 알고 가야할 부분이 "상호 배타적 집합 (Disjoint Set)"이다. DSU라고도 한다. A*에서 가장 좋은 후보를 찾을 때, 우선순위 큐를 사용을 하면 효율이 좋은 .. 2023. 8. 14. 이전 1 다음
