상호배타1 [알고리즘-15] Union-Find (합집합 찾기) 안녕하세요 기린입니다 :) 오늘은 합집합 찾기(Union-Find)에 대해 알아보도록 하겠습니다. Union-FInd는 대표적인 그래프 알고리즘입니다. 바로 '합집합 찾기'라는 의미를 가진 알고리즘인데요. 서로소 집합(Disjoint-Set) 알고리즘이라고도 부릅니다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. 위와 같이 여러 개의 노드가 서로 자유분방하게 존재한다고 생각해봅시다. 이와 같이 모두 연결되지 않고 각자 자기 자신만을 원소로 가지고 있을 때 아래 표와 같이 표현할 수 있습니다. 노드번호 1 2 3 4 5 6 7 8 부모노드번호 1 2 3 4 5 6 7 8 첫 번째 행은 '노드 번호'를 의미하고 두.. 2022. 4. 26. 이전 1 다음