Union-Find 연산의 성능 개선 어떤 요소들이 하나의 그룹으로 구성될 수 있는지 파악하기 위한 Disjoint-Set 자료구조를 처리하기 위해 Union-Find 연산을 사용한다. 이번 post에서는 union-find 연산의 성능 개선을 위한 path compression과 rank 활용에 대해 알아보자. 기본 코드는 다음과 같다. package ch07_unionfind; import java.util.Arrays; public class P01_UnionFindTree { static int[] src = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; static int[] repres = new int[src.length + 1]; // 각각의 멤버를 대표자로 하는 집합 생성 s..
Union-Find 연산의 성능 개선
Union-Find 연산의 성능 개선 어떤 요소들이 하나의 그룹으로 구성될 수 있는지 파악하기 위한 Disjoint-Set 자료구조를 처리하기 위해 Union-Find 연산을 사용한다. 이번 post에서는 union-find 연산의 성능 개선을 위한 path compression과 rank 활용에 대해 알아보자. 기본 코드는 다음과 같다. package ch07_unionfind; import java.util.Arrays; public class P01_UnionFindTree { static int[] src = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; static int[] repres = new int[src.length + 1]; // 각각의 멤버를 대표자로 하는 집합 생성 s..
2020.10.10