Algorithm/Algorithm (JAVA) (1) 썸네일형 리스트형 [JAVA] 서로소 집합(Disjoint Sets)과 연산 최근 알고리즘 문제를 풀면서 최소 신장 트리 개념에 대해 공부하다가 알게 된 크루스칼 알고리즘에서 이용되는 서로소 집합과 연산에 대해 정리해보겠습니다. 일단, 서로소는 공통으로 포함하는 원소가 없는 두 집합의 관계입니다. 아래와 같이 A, B 집합이 있을 때, 두 집합에서 공통되는 원소가 없다면 'A와 B는 서로소이다' 라고 말할 수 있습니다. 서로소 집합에서 연산은 크게 3가지가 있습니다. [ Make-Set 연산 ] >> 자기 자신인 집합을 하나 만듭니다. 즉, 자기자신이 대표원소가 됩니다. 여기서 대표원소는 부모노드가 자기자신일 때입니다. 예를 들어, 0부터 5까지 Make-Set 연산을 하게 되면 아래 그림과 같습니다. Make-Set(0) ~ Make-Set(5) [ Union-Set 연산 ] .. 이전 1 다음
