유니온파인드1 유니온 파인드(Union find) 알고리즘 개념 유니온 파인드란 합집합 찾기라는 의미로, 상호 배타적 집합(Disjoint set)이라고도 한다. 여러 노드가 존재할 때, 두 개의 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 해당 알고리즘은 find와 union 연산으로 이루어지며, find는 a가 어떤 집합에 포함되어 있는지 부모를 찾는 연산이고, union은 a와 b가 포함되어 있는 집합을 합치는 연산이다. 설명 노드 번호 1 2 3 4 5 부모 노드 1 2 3 4 5 만약 위와 같이 독립된 노드들이 있을 때 각 노드의 부모는 자기 자신이다. 노드 번호 1 2 3 4 5 부모 노드 1 1 3 4 5 이때 1과 2번 노드를 합친다(union)고 생각해보자. 부모를 합칠 때는 일반적으로 더 작은 노드를 기준으로 합치기 때문에 2의 .. 2021. 10. 10. 이전 1 다음
