'2024/11/20 글 목록

알고리즘 Union & Find 알고리즘에 관해서 정리하고자 한다.알고리즘 이름 그래도 합치고, 찾는 알고리즘이다. 대개 이 알고리즘은 노드별 연결이 되어있을때, 사이클이 존재하는가를 찾는데 많이 사용된다. 위 그림처럼 노드와 간선이 존재한다고 했을때, 해당 그래프에서 사이클이 존재하는가 아닌가를 찾아낼 수 있다.사람의 눈으로 보면 간단하게 1->2->5->1의 사이클이 보이지만 알고리즘으로는 어떻게 알게되는지 알아보자. 위와같은 과정을 거쳐 최종적으로는 모든 노드의 root는 1에 연결되어있는 결과를 얻을 수 있다. 천천히 살펴보면 1. (1-2)의 경우, 간선으로 연결되어 있어서 2의 root-node값을 1의 root-node로 바꿔준다.(여기서 1의 root-node로 변경해준 이유는 1과 ..

알고리즘 2024. 11. 20. 21:24

이전 1 다음