union-find (1) 썸네일형 리스트형 124. Disjoint Set & Union-Find 이번에 다루는 내용은 트리 구조를 응용한 것이다. 집합론에서 분리 집합(Disjoint Set)은 공통 원소가 없는 두 집합을 의미한다. 컴퓨터과학에서 이 개념은 한 개 이상의 집합으로 확장되며, 한 개의 집합 또는 어떤 두 집합도 공통 원소를 갖지 않는 두 개 이상의 집합을 분리 집합이라고 생각하면 된다. $0$개의 집합 같은 경우는 생각하지 않는다. 분리 집합은 아래의 두 가지 연산에 의해서 여러 활용도를 갖게 된다. 두 집합을 하나로 합친다. (Union) 원소가 현재 어떤 집합에 속해 있는지 확인한다. (Find) 이 두 연산의 이름을 따서 유니온-파인드(Union-Find)라는 이름이 생겨났다. 이 개념을 PS의 관점에서 보면, 일단 각각의 집합은 서로 구별이 가능한 식별자를 갖고 있어야 한다... 이전 1 다음
