728x90 반응형 분리 집합1 [백준] 분리집합(유니온-파인드) 백준 문제 풀이 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 분리 집합 알고리즘 -교집합이 존재하지 않는 두개 이상의 집합을 뜻한다. -같은 집합에 속한 원소들을 O(1)의 시간 복잡도로 확인하는 방법으로 사용된다. -따라서 같은 집합에 속한 부모 값을 기준으로 두 집합을 Union(합)-Find(찾기)를 진행한다. -대표값(부모 노드)를 찾아 이용한다. Union 연산 -합집합 연산으로 a, b 두 개.. 2023. 6. 24. 이전 1 다음 728x90 반응형