유니온 파인드 C++ (1) 썸네일형 리스트형 Union-Find(유니온 파인드)에 대해 알아보고 구현하기 Union-Find? 유니온 파인드. 그대로 해석하면 union은 조합, find는 찾다로 해석이 가능하다. 실제로 이 알고리즘은 두 연산 find와 union를 사용한다. 여러 개의 노드가 있다고 가정했을 때 2개의 노드를 union을 통해 합치는 것도 가능하고, find를 통해 해당 노드의 부모노드를 찾는 것 또한 가능하다. 전체적인 구현 방법 노드들의 부모를 나타낼 배열을 선언해줘야한다. 예를 들어 트리를 다룬다고 했을 때 직접적으로 간선을 옮겨주는 식으로 할 수 없는가? 라는 생각을 가질 수 있으나, 가능은 하나 노드들의 부모가 하나로 통일됬는 지 검사하는 등의 연산이 필요할 경우, 시간복잡도가 난해해지므로 O(n)으로 끝낼 수 있게 노드들의 부모를 나타낼 배열을 선언해줘야한다. 부모노드가 없을 .. 이전 1 다음
