코딩 테스트 스터디 - 10 집합

상호배타적 집합

• 교집합이 없는 집합관계.집합 표현하기어떤 집합의 원소가 하나의 집합의 원소라는 것을 알 수 있어야 한다.
  각 집합 간 다른 집합이라는 것을 알 수 있어야 하고,
  특정 원소가 어느 집합에 속하는지 알 수 있어야 함.
  두 집합을 하나로 합칠 수 있어야 함 => 대표 원소를 설정한다면?

: 각 집합에서 가장 작은 원소를 대표 원소로 설정한다.

집합의 연산

find

특정 노드의 루트 노드를 확인.

필요한 경로 깊어질 경우 연산 늘어남. 경로 압축으로..

• find연산을 하는 노드가 루트 노드라면 루트 노드 반환.
• find연산을 하는 노드가 루트 노드가 아니라면, 자신의 부모 노드를 find로 설정

거쳐가지 않으면 시간복잡도가 O(1)이 되지는 않음 ...

union

두 집합을 하나의 잡합으로 합친다.
작은 루트 노드 쪽으로 합치는 게 쉬운 방법

집합의 구현

• 노드의 최댓값이 별로 안 크면 => 배열로 구현
• 크면 => unoredered_map으로
• 대부분은 경로 압축, 랭크 기반까지 구현할 필요는 없다.

집합 알고리즘은 언제 쓰나?

• 이미지 세그멘테이션. 이미지에서 각 객체마다 분할해서 다른 색을 칠하고 있다. 각 객체마다 구분이 되어야 함

출처 : 코딩 테스트 합격자 되기

https://www.youtube.com/watch?v=pQ4fcGEG-PY