알고리즘 이론/유니온 파인드 알고리즘1 유니온 파인드(Union-find) 알고리즘 유니온 파인드(Union-find) 알고리즘 Disjoint Set(서로소 집합)을 표현하기 위해 사용한다 (트리 구조를 활용함) 서로 중복되지 않은 부분집합끼리 연결했을 때 사이클이 생기는지 아닌지를 판단할 수 있는 알고리즘 더욱 간단하게, 노드들이 하나의 집합에 속해 있는지 찾거나, 노드들을 서로 연결하기(합치기) 위해 사용 2. 알고리즘의 구현 초기화: n개의 원소를 독립적인 집합으로 구분 초기화 find 함수: 두 개의 노드가 같은 집합(그래프)에 속하는지 확인하기 위해, 루트(최상위 부모) 노드를 찾는 로직 union 함수: 두 집합을 하나의 집합으로 합침(두 트리를 하나의 트리로 연결) 시간 복잡도 최악의 경우(아무 규칙 없이 구현할 경우) O(n) union-by-rank와 path-comp.. 2020. 10. 10. 이전 1 다음