728x90 반응형 Union-find1 Union-Find(합집합 찾기) Union-Find 는 대표적인 그래프 알고리즘이다. Disjoint-Set이라고 해서 서로소 집합 알고리즘이라고도 부른다. 여러 개의 노드가 존재할 때, 두 개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는 지 판별하는 알고리즘 처음에 여러 개의 노드가 서로 자유롭게 존재한다. 이와 같이 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 첫 번째 행은 '노드 번호'를 의미하고 두 번째 행은 '부모 노드 번호'를 의미한다. 즉, 자신이 어떠한 부모에 포함되어 있는지를 의미한다. 이와 같이 1과 2가 연결되었다고 한다. 이러한 '연결성'을 우리가 프로그래밍 언어로 어떻게 표현할 수 있을 지에 대한 내용이 바로 Union-Find라고 생각하자. 2번째 인덱스의 값에 '.. 2019. 4. 26. 이전 1 다음 728x90 반응형