[Step 5] 집합

상호 배타적 집합

⇒ 교집합이 없는 집합 관계

집합 표현하기

고려사항

1. 특정집합 원소들이 하나의 집합의 원소라는 것을 알 수 있어야함

    ex) a={1,2,3}일때 각 원소가 집합 a에 속한다는 걸 알아야함

2. 각 집합 간 다른 집합이라는 것을 알 수 있어야함

    ex) a={1,2,3} b= {4,5,6} 두 집합이 다른 집합이라는걸 알아야함

3. 특정 원소가 어느 집합에 속하는지 알아야함

    ex) a={1,2,3} b= {4,5,6} 원소 5가 집합 b에 속하는걸 확인 가능해야함

4. 두개의 집합을 하나로 합칠 수 있어야 함

⇒ 각 집합의 대표원소(루트노드) 를 만들면 해결!

 

집합의 연산

집합의 연산 find

⇒특정 노드의 루트노드를 확인하는 연산

특정 노드로 부터, 루트노드가 나올때 까지 거슬러 올라가면 됨.

find(7)하는 경우

find(7) ≠ find(6) ≠find(2) ≠find(1) —> 노드의 값과 부모노드의 값이 같을 때 까지 계속 find

방법 1. (find(1)의 리턴값을 find(2)에다가 넣음 ex) find(find(1)) …….find(find(6)) 각 찾을 find()안에 값을 변경해버리는 것)

방법 2. 마지막에 find(1)을 그냥 리턴하는 것

 

find 최악의 경우

⇒ find(N) 너무 비효율적!

⇒경로 압축 알고리즘을 활용하여 오른쪽과 같이 변경해 보자!

경로압축 과정

⇒ 그냥 부모 노드가 1로 치환이 되는 모습

경로 압축을 하면 O(N) → O(1) 까지도 준다

 

다른 경우

 

집합의 연산 union

⇒두 개의 집합을 하나의 집합으로 합치는 연산

⇒ find를 이용해 대표 원소를 구하고 루트노드를 하나로 통일

여러가지 방법이 있지만 작은 루트노드 쪽으로 합치는 방법도 있다.(예시 위 그림)

 

효율성

union 연산 이후 깊이를 최소화 하는 방법?

집합에 랭크를 도입 => 특정노드 기준 최대 깊이

랭크가 더 큰쪽으로 합쳐서, 랭크의 증가를 최소화 하자! 

랭크기반 알고리즘

⇒랭크 기반으로 랭크가 더 높은쪽으로 합쳐야함.

 

집합의 구현

노드의 최대값이 크지 않은 경우 =⇒ 배열

노드의 최대값이 큰 경우 =⇒ unordered_map으로 구현

—> 대부분 코테에서는 경로압축, 랭크기반 까지는 구현 X

 

출처

 

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런