[2021/08/03][짤막한 이야기 - 유니온 파인드]

[2021/08/03][짤막한 이야기 - 유니온 파인드]
“유니온 파인드(Union-Find)”이란 어떠한 그룹에서 여러 노드가 존재할 때 임의의 두 노드를 하나의 그룹으로 병합(Union)하고, 임의의 노드가 어떤 그룹에 속하는지 탐색(Find)하기 위한 알고리즘이다.
즉, 병합과 탐색을 주된 연산으로 하며 병합은 2개의 노드 X와 Y의 그룹명을 합치는 역할을, 탐색은 1개의 노드 Z의 그룹명을 출력하는 역할을 한다.
알고리즘 구현 문제에서는 주로 어떤 팀과 어떤 팀이 동맹관계인지 확인하거나 할 때에 응용할 수 있다.
특정 그룹을 탐색하기 위한 방법으로는 꼭 “유니온 파인드”를 적용하지 않아도 “전수 조사(Brute Force)”가 가능하지만, 이 경우 높은 확률로 많은 시간이 소요되게 된다.
그림의 예시에서는 두 그룹이 존재한다.
“Find” 결과로 1, 2, 3, 4 노드가 동일한 그룹명 1(제일 낮은 노드 번호)을 출력하며, 5, 6 노드가 동일한 그룹명 5를 출력한다.
“Union”은 꼭 그룹명을 입력값으로 할 필요가 없기 때문에 6번 노드와 3번 노드를 “Union”하는 경우 5, 6 노드의 그룹명이 5에서 1로 변경된다.
#이야기 #루니프 #알고리즘 #유니온파인드 #근원찾기

[2021/08/03][Short Story - Union-Find]
“Union-Find” is an algorithm for merging arbitrary two nodes into one group when there are multiple nodes in a certain group, and finding which group a random node belongs to.
That is, union and find are the main operations, union plays a role of merging the group names of two nodes X and Y, and find plays a role in outputting the group name of one node Z.
In the algorithm implementation problem, it can be mainly applied when checking which team and which team is an alliance.
As a method to search for a specific group, “Brute Force” is possible without applying Union-Find, but in this case, it takes a lot of time with high probability.
In the example in the figure, there are two groups.
As a result of the “Find”, nodes 1, 2, 3, and 4 output the same group name 1 (lowest node number), and nodes 5 and 6 output the same group name 5.
“Union” does not necessarily require the group name as an input value, so when “Unioning” nodes 6 and 3, the group names of nodes 5 and 6 are changed from 5 to 1.
#Story #LootNiP #Algorithm #UnionFind #FindRoot