Union-Find

velogmj·2021년 10월 4일
0

Algorithm

목록 보기
7/8

📌서로소 집합 (Disjoint-Set)

  • 서로소 집합 (Disjoint-set)
  • 서로 중복 포함된 원소가 없는 집합들. 교집합이 없는 집합들
  • 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. = 대표자
  • 서로소 집합을 표현 하는 방법
    • 연결 리스트
    • 트리

💡서로소 집합 (연결리스트)

  • 같은 집합의 원소들은 하나의 연결리스트로 관리
  • 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
  • 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.
  • union(e,f) = e가 속한 집합에 f가 속한 집합이 흡수된다!

💡서로소 집합 (트리)

  • 하나의 집합을 하나의 트리로 표현한다.
  • 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.

  • 연결리스트를 구현하는것은 번거롭기 때문에 자신의 집합에 속해있는 부모의 관계를 이용해 배열로 만든다.
  • 부모를 가리키는 집합이기 때문에 보통 parents라고 명명한다.

📌UnionFind 알고리즘

💡서로소 집합 연산

  • Make-Set(x)
    • 가장 작은 단위의 단위 집합을 만드는 연산
    • 원소 모두 각각 개별의 집합을 만들고 시작한다.
  • Find-Set(x)
    • 대표자를 찾는 연산
  • Union(x,y)
    • x가 속한 집합과 y가 속한 집합을 합치는 연산

💡연산의 효율을 높이는 방법

  • Rank을 이용한 Union
    • 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크라는 이름으로 저장한다.
    • 두 집합을 합칠 때 랭크가 낮은 집합을 높은 집합에 붙인다.
  • Path compression
    • Find-set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾼다.
    • Find-set을 행할 때 일어나기 때문에 Find-set을 하기 전까지는 바뀌지 않는다.

profile
내가 보려고 쓰는 블로그 :)

0개의 댓글