quick union (3) 썸네일형 리스트형 [JAVA] Quick Union Improvements 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;) 저번 포스팅에서 다뤘던 Quick Union은 Quick Find에 비해 union 연산이 빠르다는 장점을 다뤘지만, 트리의 크기가 커질 수 있다는 단점을 가지고 있었습니다. 이번 포스팅에서는 Quick Union에서 트리의 크기에 따라 발생할 수 있는 문제를 해결하는 알고리즘에 대해 알아보겠습니다. 첫 번째 개선 알고리즘은 Weighted 알고리즘입니다. 이 알고리즘은 union 연산에서 트리를 만들 때, union 연산에서 매개변수로 받는 인자들의 순서에 관계 없이, 더 작은 트리를 가진 쪽이 더 큰 트리를 가진 쪽의 자식 노드로 들어가는 방법입니다. 이를 통해 크기가 큰 트리가 작은 트리의 자식 노드로 들어가 트리의 크기.. [JAVA] Quick Union 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요 ;) 이전 포스팅에서 다뤘던 Quick Find 알고리즘은 union 연산에 있어서 모든 배열에 한 번씩 접근을 해야 하기 때문에 시간 비용 측면에서 매우 비싸고expensive 비효율적이라는 사실을 확인했습니다. 이번 포스팅에서는 그 union 연산을 조금 더 효율적으로 처리할 수 있는 Quick Union 알고리즘에 대해 알아보겠습니다. Quick Union 알고리즘은 루트(root)라는 개념을 사용합니다. union 연산을 처리할 때 연결된 모든 멤버들에 접근하여 값을 변경하는 것이 아니라, union 연산을 통해 연결을 할 때 자식 노드로 멤버를 저장시키고 자신은 root가 되는 방식입니다. 이 그림을 보면 Quick Un.. [JAVA] Quick Find 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;) Quick-Find는 위와 같이 하나의 배열이 존재할 때, 그 배열의 인덱스에 저장된 값들을 다른 인덱스에 저장된 값들과 연결시키고(union), 또 연결되었는지 확인하는(connected) 알고리즘의 한 유형입니다. 그 구조를 도식화한 것이 위의 그림입니다. Union의 기본 구조는 위와 같습니다. union()에 두 인덱스 값을 줬을 때, 앞의 인덱스에 저장된 값을 뒤의 인덱스에 저장된 값으로 변경하는 방식입니다. public class QuickFind { private int[] id; public QuickFind(int N){ id = new int[N]; for(int i=0; i 이전 1 다음
