2023.04.18
2023. 4. 18. 23:45ㆍ회고록
728x90
그래프변태가 돼었다...
기본 탐색은 골3 정도까지는 건드려 볼 수 있는 수준이 된 것 같아 그래프를 졸업하고 정렬을 들어갈까 했지만 그래프 이론이라는 파트가 따로 있어서 그 부분을 먼저 건드려 본 다음에 다른 것을 해보기로 했다.
앞으로 할 그래프 이론 알고리즘은 아래와 같다.
1. 분리집합, 서로소 집합(Disjoint Sets, Union-Find)
2. 신장 트리 (MST, LST)
3. 크루스칼 알고리즘
4. 위상 정렬 알고리즘
오늘은 네가지 알고리즘 중 분리집합에 대해 공부했고, 기본 문제 하나를 풀어보았다.
1717번: 집합의 표현
초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작
www.acmicpc.net
두가지 연산을 하는데 Union(합집합)과 Find(찾기)를 통해서 자신이 속한 트리의 루트노드를 재귀적으로 찾는 알고리즘이다.
최소 신장 트리를 찾는 크루스칼 알고리즘에서 사용하므로 매우 중요하다고 볼 수 있으며, 아이디어 또한 간단하여 구현하기 크게 어렵지 않았다.
우선 골5 문제를 풀었고 오늘은 시간이 부족하므로 다음 문제를 모두 푼다면 다른 알고리즘으로 넘어갈 생각이다.
추천 문제
[출처] 유니온 파인드(Union-Find) (수정: 2020-08-03)|작성자 라이
728x90
'회고록' 카테고리의 다른 글
| 2023.04.17 (0) | 2023.04.27 |
|---|---|
| 2023.04.23 (0) | 2023.04.22 |
| 2023.04.13 (0) | 2023.04.13 |
| 2023.04.10 오랜만에 회고록 (0) | 2023.04.10 |
| 2023.04.01 (0) | 2023.04.01 |