알고리즘

이제 우리는 이 동적 연결 문제를 해결하기 위해 Quick-find라 불리는 알고리즘의 첫 번째 구현을 살펴보겠다.이것은 연결 문제를 해결을 위한 조급한(eager) 알고리즘이라 불린다.우리는 이 알고리즘을 위해 단순한 정수 배열로 된 객체를 자료구조로 사용할 것이다.

문제를 모델링하기 이 단계에서는 풀 필요가 있는 문제의 주요 요소들이 무엇인지를 기본적으로 이해해야 한다. 그럼 문제를 풀 몇몇 알고리즘을 떠올릴 수 있다. 많은 경우에, 우리가 처음 떠올린 알고리즘은 (그럭저럭 사용하기에) 충분히 빠르고 메모리 문제도 없을 것이라서,

이전글에서 설명한대로 QuickFind는 큰 문제에 대해서는 너무 느리다. 그래서 어떻게 더 잘할 수 있을까? 우리의 첫 번재 시도는 Quick-union이라고하는 대안이다. Quick-union [lazy approach] 이 방식은 알고리즘 설계에서 (조급한(ea

이전글까지 quick-union과 quick-find 알고리즘을 살펴봤다. 둘 다 구현은 쉽지만, 아주 큰 동적 연결성(dynamic connectivity) 문제를 해결할 순 없다. 그렇다면 우린 이걸 어떻게 향상시킬 수 있을까? 이에대해서 한번 살펴보도록 하자.

엄청난 수의 union-find 응용들이 있다. 앞서는 네트워크에서의 동적 연결성에 대해 언급했었는데, 컴퓨터 인프라엔 다른 예가 많이 있다. 중요한 예로, 맨 아래를 보면 이미지 처리 분야에서 이미지 내의 영역(연결 컴포넌트에 대응)에 레이블(label)을 지정하는