union-find

union-find

    6. Union Find(합집합 찾기) : MST - 1

    Union Find (합집합 찾기) MST - 1 정말 오랜만에 포스팅이다. MST 알고리즘 문제를 풀던 도중 생각나서 포스팅 하게 됐다. 매주 주말마다 알고리즘 개념 정리를 하려고 하는데 계속 실패하는 것 같다... ㅎㅎ;; 오늘 다뤄볼 주제는 MST, 최소 신장 트리 문제를 해결하기 위한 기본 베이스인 Union Find이다. 최소 신장 트리 문제를 해결하기 위한 방법에는 대표적으로 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 존재한다. Union FInd는 크루스칼 알고리즘의 핵심이라고 말할 수 있다. 그럼 Union Find가 무엇인지 알아보자. Union Find는 말 그대로 Union, 집합을 찾는 알고리즘이다. 그래프 정보가 주어졌을 때 이들 간의 관계를 알아볼 수 있다. 바로 예시..