Algorithm
[Algorithm] 서로소 집합(Disjoint Set) 알고리즘
서로소 집합 먼저 중학생 때 배웠던 서로소를 떠올려보자. 어떤 두 수 A와 B가 있을 때, 두 수의 공약수가 1을 제외하고는 존재하지 않는 수를 서로소라고 부른다. 이를 고등학생 때 배운 집합의 개념을 빌려 그림으로 표현해 보자. 위의 그림은 24와 49의 약수를 벤다이어그램으로 표현한 것이다. 그림을 보면 둘의 공약수가 오직 1만 존재하는 것을 볼 수 있으며, 이런 형태의 수를 서로소라고 부른다. 이제 집합에서의 서로소가 무엇을 의미하는지 알아보자. 정수에서 서로소는 서로의 약수가 1을 제외하고 겹치지 않는 것을 의미했다. 이와 유사하게 서로소 집합은 두 집합의 원소가 겹치지 않는 것을 의미한다. 예를 들면 아래의 그림과 같은 집합을 서로소 집합이라 부를 수 있다. 위의 두 집합 A와 B를 보면, 두 ..
