[코딩 테스트 합격자 되기] 집합

[인프런] 코딩 테스트 합격자 되기 C++

강의 링크 : https://www.youtube.com/watch?v=pQ4fcGEG-PY

 

[목차]

• 상호배타적 집합이란?
• 집합의 연산
  • union 연산과 find 연산
  • 경로압축 / 랭크기반 알고리즘으로 개선하기
• 집합의 구현

---

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

 

[집합의 표현]

 

[집합의 연산]

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

- 특정 노드부터 루트노드가 나올 떄까지 거슬러 올라가기

- union 연산에서도 활용됨

- 경로 압축 : find 연산을 할 때 루트노드를 찾는 과정에서 거쳐간 노드들의 경로 압축

   - 경로 압축 후 find 연산의 시간 복잡도 : O(N) -> O(1)

 

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

- find 연산을 통해 각 집합의 대표원소를 구하고, 루트노드를 하나로 통일

1. 작은 루트 노드쪽으로 합치는 방법

2. 랭크기반 알고리즘

   - 루트노드의 랭크를 낮게 유지하는 방향으로 합치는 방법

   - 랭크가 더 높은쪽으로 합치기

 

[집합의 구현]

• 노드의 최대값(총 개수를 의미)이 크지 않은 경우 => 배열로 구현
• 노드의 최대값이 큰 경우 => unordered_map으로 구현
• 대부분의 코테 문제는 경로압축, 랭크기반까지 구현할 필요는 없다

배열로 구현한 union & find 알고리즘

- 경로압축, 랭크기반 포함 : https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/unionfind.cpp

- 경로압축, 랭크기반 제거 : https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/unionfind_not_optimization.cpp

unordered_map으로 구현한 union & find 알고리즘 : https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/unionfind_with_unordered_map.cpp

* map을 쓰면 key값을 삽입할 때마다 매번 정렬하기 때문에 시간초과 날 수 있음. 집합에서는 필요없는 정렬이므로 unordered map 사용하기

 

[집합 알고리즘 언제 사용?]

• 이미지 세그멘테이션 - 각 이미지를 의미있는 부분으로 분할
• 네트워크 연결성 확인 - 대규모 네트워크에서 두 컴퓨터가 서로 연결되어있는지 확인
  • 문제 예시 : https://github.com/dremdeveloper/codingtest_cpp/blob/main/Example/network_connectivity_union_find.cpp

 

---

추천 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42861