본문 바로가기
반응형

union-find2

[Python] 백준 1717번 - 집합의 표현 (골드 5) https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 혼자 힘으로 풀었는가? X 알고리즘 분류 - 자료 구조 - 분리 집합 문제 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. 입력 첫째 줄에 $n$, $m$이 주어진다. $.. 2023. 9. 5.
분리 집합 (Disjoint Set) : Union-Find 알고리즘 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 위 문제를 풀다가 몰라서 정리하고 간다. Union-Find 알고리즘은 분리 집합(Disjoint-set) 자료구조를 구현하는 데 사용된다. Union: 두 개의 집합을 하나로 합치는 연산. 두 집합을 합치기 위해 루트를 찾아서 하나의 집합으로 만듦. Find: 주어진 원소가 주어진 집합의 루트를 찾는 연산. 이 연산을 통해 두 원소가 같은 집합에 속해 있는지.. 2023. 9. 5.
반응형