J.BF Story

서로소 집합(Disjoint Set) 이란?서로소 집합은 서로 공통 원소가 없는 둘 이상의 집합들을 의미한다.고등학교 때 반 별로 나눠 운동회를 진행했던 것을 생각하면 이해가 쉬울 것같다.보통 가장 효율적인 트리 구조를 이용해서 구현한다. 유니온 파인드란(Union Find) 이란?유니온 파인드는 서로소 집합을 만들 때 사용하는 알고리즘이다.각 집합에는 대표 번호를 가지며 2가지 연산을 통해 두 집합을 합치거나 해당 집합의 대표 번호를 찾을 수 있다.union(a, b): a와 b의 집합을 합친다.findSet(a): 대표번호(트리에서는 최상위 부모)를 찾아 반환한다.💡findSet의 경로 압축findSet구현 시 경로 압축을 사용하여 속도를 더 빠르게 할 수 있다경로 압축을 사용하지 않은경우, 트리 구..