유니온 파인드 ( Union-find )
Table of Contents 개요초기화간단한 방법최적화 단계 1최적화 단계 2 - 유니온 파인드 트리유니온 파인드 트리 - 코드문제 1. 개요 유니온 파인드는 집합을 관리하는 자료구조로서, disjoint set 이라고 부르기도 합니다. 이 자료구조를 활용하면 아래의 두 가지 연산을 사용할 수 있습니다. 연산 1) 요소 A와 요소 B가 같은 집합에 속하는 지 확인.연산 2) 요소 A가 속한 집합과 요소 B가 속한 집합을 병합. 유니온 파인드 연산의 이해를 위해 일단, 위와 같이 4개의 요소가 있다고 해보겠습니다. 초기 상태는 아직 병합을 한 번도 안 한 상태이기 때문에 각자 다른 집합에 속합니다. 이 상태에서 1번 연산, 예를 들어 요소 1과 요소 2가 같은 집합 인지에 대한 질의가 들어오면 이 자료..
그래프 ( Graph )
2017. 11. 21. 21:50