- 집합이란?

집합 : 순서와 중복이 없는 원소들을 갖는 자료구조

상호배타적 집합에 대해 알아보자.

집합은 특성에 따라 부르는 말이 다양하다

유한 집합(원소 개수가 유한한 집합), 무한 집합(원소 개수가 무한한 집합), 공집합(아무 원소도 없는 집합)

 

오늘 살펴볼 집합은 다양한 종류의 집합들 중 "상호배타적 집합"에 대해서만 말해보려고 한다.

 

"상호배타적 집합" : 교집합이 없는 집합 관계

 

 

사진을 통해 상호배타적 집합인 경우와 그렇지 않은 경우에 대해 알아볼 수 있다.

 

 

 

 

즉, 공통 원소가 있어서 교집합이 있는 집합의 경우 상호배타적이지 않는 집합이라고 말할 수 있다.

 

 

배열을 활용한 트리로 상호배타적 집합 표현하기

집합은 배열을 활용한 트리로 구현이 가능하다.

트리를 구현하기 위해서는 루트 노드가 필요한데, 집합에서의 대표 원소를 통해 루트 노드를 표현한다.

 

 

집합을 트리 형태로 표현하기 위한 규칙은 다음과 같다.

  • 배열의 인덱스는 자신을, 배열값은 부모 노드를 의미한다.

 

그림을 통하여 더 자세히 알아보자.

 

 

 

단계별로 표현하면 다음과 같다.

 

 

 

유니온-파인드 알고리즘 살펴보기

집합 알고리즘에 주로 쓰이는 연산은 합치기(Union)와 탐색(Find)이다.

이 둘을 묶어 유니온-파인드 알고리즘이라고 하는데

이름 순서로는 유니온 연산이 먼저 나오지만 파인드 연산을 알아야 유니온-파인드 알고리즘을 이해하기가 쉽다.

 

파인드(Find, 탐색) 연산

- 특정 노드의 루트 노드가 무엇인지 탐색하는 방법

   => 특정 노드들이 같은 집합에 있는 지 확인할 때 사용 (A, B 두 노드의 루트 노드가 같다면 같은 집합에 속한 것)

 

 

 

유니온(Union, 합치기) 연산

- 두 집합을 하나로 합치는 연산

   => 두 집합의 루트 노드를 같게 함

 

 

 

 

 

따라서 유니온-파인드 알고리즘을 코드로 표현하면 다음과 같다.

 

// 1. union: x와 y가 속한 두 집합을 합침
function union(tree, x, y) {
  x = find(tree, x)
  y = find(tree, y)
  tree[y] = x
}

// 2. find: x가 속한 집합의 대표 원소를 찾음
function find(tree, x) {
  // 만약 본인이 루트 노드라면 본인을 반환
  if (tree[x] === x) return x

  // 그렇지 않다면, 본인의 부모 노드를 find()에 재귀 호출
  tree[x] = find(tree, tree[x])
  return tree[x]
}

// 연산을 모두 수행한 후 집합의 개수를 반환
function solution(k, operations) {
  let tree = Array.from({ length: k }, (_, i) => i)

  operations.map((op) => {
    if (op[0] === 'u') union(tree, op[1], op[2])
    else find(tree, op[1])
  })

  return new Set(Array.from({ length: k }, (_, i) => find(tree, i))).size
}

 

티스토리툴바