목록2023/10/05 (1)
Rootable의 개발일기
유니온 파인드(union-find) 알고리즘
여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘 📌 union, find 연산 union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b) == A U Bfind 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환 📌 원리 🔎 1차원 배열 1차원 배열을 통해 초기 배열을 생성한다. 초기 배열은 인덱스가 곧 값이 되며, 이는 각 노드가 속한 집합이 없어 자신이 대표 노드가 된 상태인 것이다. 🔎 union 연산 2개의 노..
알고리즘
2023. 10. 5. 16:12