Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- Spring
- 싸피
- 알고리즘
- SWEA
- 유니온파인드
- SSAFY
- JPA
- 그리디
- 백준
- DP
- JUnit
- 코테
- 부분수열의합2
- database
- 그래프
- 코딩테스트
- 완전탐색
- 다익스트라
- 완탐
- 다시보기
- 알고리즘기본개념
- 자바
- BFS
- 트러블슈팅
- 코드트리
- Union Find
- 코딩테스트실력진단
- Java
- 기본유형
- DFS
Archives
- Today
- Total
목록Union Find (1)
HwangHub
자바로 알고리즘 시작하기 7 - Disjoint Set (Union Find)
오늘은 서로 중복된 원소가 없는 '분리 집합 or 서로소 집합(Disjoint Set)'에 대해 알아보고, 이를 이용하여 노드 간의 연결 여부를 판별하는 'Union Find' 알고리즘에 대해 알아보겠습니다. 이 두 가지는 그래프 알고리즘에서 중요하게 다루어지며, 특히 최소신장트리(Minimum Spanning Tree)를 구현하는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘에서 활용됩니다. 먼저, Disjoint Set은 각각의 원소가 하나의 집합을 이루며, 교집합이 존재하지 않는 집합을 말합니다. 이를 연결 리스트나 트리를 통해 표현할 수 있지만, 보통 트리 구조를 사용하여 구현합니다. 분리 집합을 표현하기 위해 각 노드가 바라보는 부모 노드를 나타내는 parent[] 배열을 사용합니..
CS-STUDY/자료구조 & 알고리즘
2024. 2. 21. 11:12