유니온 파인드 알고리즘

저번 포스팅에서 집합 개념을 정리했다

• 집합 알고리즘의 메인 연산 : 합치기, 탐색

합치기는 union, 탐색은 find라고 불러서 유니온파인드 알고리즘이라고 함

find와, union 연산을 각각 알아보자

 

1. 파인드 연산

• 특정 노드의 루트 노드가 뭔지 탐색하는 방법임
• 보통, find 연산은 특정 노드가 같은 집합에 있는지 확일할 때 씀
  • 예) a,b 노드가 있는데 얘네의 루트 노드가 같다면 얘네는 같은 집합임
  • 1) 현재 노드의 부모 노드를 확인
  • 2) 부모 노드 계속 확인하다가 부모 노드가 루트노드이면 찾기 종료
  • 3) 아니라면 계속 반복

1.1. find 예시 

• 7을 찾아보자! find(7)

• 1) 7의 루트노드를 찾는다. -> (루트노드는 인덱스랑 밸류가 같음)
• 2) 루트 노드 찾기 전까지 계속 반복하고 찾으면 find 종료하면 됨
• -> 이것은..? 재귀!

하지만 얘는 최악의 경우 시간 복잡도가 O(N) <- 이게 무슨 말이냐 하면..!

이런 경우가 바로 O(N)

 

즉, 우리는 루트노드를 찾는게 중요하지 부모 노드를 하나하나 다 찾을 필요는 없단 말씀!

• 어떻게? 집합형태 유지하면서 트리 높이를 줄인다(경로압축)

바로 이렇게!

 

 

2. 합치기 연산

• 두 집합을 하나로 합치는 연산
• 이게 무슨 말이냐? -> 두 집합의 루트 노드를 같게 함
  • 어떤 걸로 루트노드를 하냐면 둘 중 하나면 됨!
• 정리하자면
  • 1) find 연산으로 두 집합의 루트 노드를 찾음
  • 2) 찾은 두 루트 노드 값 비교
  • 3) 두 집합을 합침(루트 노드를 같게 함. 둘 중 아무거나)
• 예시

얘네 각각 루트노드가 1이랑 2임 집합B의 루트노드를 1로 만들어 보장

 

합치기 연산은 트리 깊이가 깊을 수록 연산 비용이 커짐 -> 랭크!!!

2.1. 랭크란?

• 현재 노드 기준으로 가장 깊은(아래쪽으로) 노드까지의 경로 길이

4랑, 3은 단말노드라 더 들어갈 깊이가 없어서 0, 2는 1, 1은 2

 

2.2. 랭크 기반 합치기 연산

1) 두 노드의 루트 노드를 구함

2) 루트 노드의 랭크를 비교 -> 랭크 값이 큰 루트 노드를 기준으로 삼기, 같으면 아무거나 

 

왼쪽 집합이 랭크 값이 더 큼! 그럼 왼쪽을 기준으로