disjoint set2 [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. [Algorithm] Disjoint Set의 표현: Union-Find (합집합 찾기) Disjoint Set (서로소 집합) 'Disjoint set'는 공통 원소가 없는 부분 집합들이다. 어떤 교양 대면 수업에 여러 학과 사람들이 모여있다고 해보자. 이때 교수님이 갑자기 같은 과 사람들끼리 조를 만들라고 한다. 그럼 학생들은 이리 저리 돌아다니다가 같은 과 사람을 찾으면 팀을 이뤄 같이 움직이게 될 것이다. 그리고 팀끼리도 같은 과인 것을 확인하면 두 팀은 합쳐진다. 만들어진 조들은 공통 원소가 없는 부분 집합들, disjoint set이 된다. 이 상황을 자료구조로 표현한 것이, 즉, disjoint set에 대한 정보를 저장하고 조작하는 자료 구조가 'Union-Find'다. Union-Find 알고리즘 (합집합 찾기) 대표적인 그래프 알고리즘으로 합집합 찾기라고도 불리며, 서로소 .. 2023. 3. 17. 이전 1 다음
