https://www.inflearn.com/course/cpp-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9
집합
- 상호배타적 집합이란?
- 집합의 연산
- union 연산과 find 연산
- 경로 압축 / 랭크 기반 알고리즘으로 개선하기
- 집합의 구현
상호배타적 집합
- 교집합이 없는 집합관계(집합은 꼭 2개가 아니라 N개일 수도 있음)
집합 표현하기
무엇을 고려해야 할까?
- 특정 집합 원소들이 하나의 집합의 원소라는 것을 알 수 있어야 함.
- 집합 A = {1, 2, 3}일 때 각 원소가 집합 A에 속한다는 것을 알아야 함.
- 각 집합 간 다른 집합임을 알 수 있어야 함.
- 집합 A = {1, 2, 3}, ㅠ = {4, 5, 6}일 때 두 집합이 다른 집합임을 알아야 함.
- 특정 원소가 어느 집합에 속하는 지 알 수 있어야 함.
- 집합 A = {1, 2, 3}, B = {4, 5, 6}일 때 원소 5가 집합 B에 속함을 확인 가능해야 함.
- 두 개의 집합을 하나로 합칠 수 있어야 함.
- 집합 A = {1, 2, 3}, B = {4, 5, 6}일 때 이를 합쳐서 {1, 2, 3, 4, 5, 6}을 만들 수 있어야 함.
main idea - 각 집합의 대표 원소를 만들면 해결된다.
대표 원소
각 집합에서 가장 작은 원소를 대표원소(루트 노드)로 한다.
ex) 집합 A = {1, 2, 3}, B = {4, 5, 6}일 때 A의 대표 원소는 1, B의 대표 원소는 4
- 대표 원소는 현재 노드와 부모 노드가 같음
- 배열로 나타낼 수 있음(현재 노드는 인덱스, 부모 노드는 값)
- 부모 노드가 없다면 -1로 나타낼 수 있음
집합의 연산
find
특정 노드의 루트 노드를 확인하는 연산
- 특정 노드로부터, 루트 노드가 나올 때까지 거슬러 올라가면 됨
- union연산에서도 활용됨
find의 최악의 경우
- 루트 노드를 찾는데 필요한 경로가 길어질 경우 연산 횟수가 증가함 O(N)
- 어떻게 하면 경로의 깊이를 줄일 수 있을까?
- → 경로 압축 알고리즘 활용!
find 경로 압축
find 연산을 하는 노드가 루트 노드일 경우, 루트 노드 반환
find 연산 하는 노드가 루트 노드가 아닐 경우, 자신의 부모 노드를 find(해당 노드의 부모 노드)로 설정
union
두 개의 집합을 하나의 집합으로 합치는 연산
find 연산을 통해 각 집합의 대표 원소를 구하고 루트 노드를 하나로 통일
→ 여러 방법이 있지만 작은 루트 노드 쪽으로 합치는 방법도 있음
효율성에 대한 고민
union 연산 이후 깊이 최소화할 수 있을까?
→ 집합에 랭크를 도입하자!(특정 노드 기준 최대 높이)
→ 랭크가 더 큰 쪽으로 합쳐서, 랭크의 증가를 최소화하자(랭크 기반 알고리즘)
랭크 기반 알고리즘
집합의 구현
- 노드의 최대값이 크지 않은 경우 → 배열
- 노드의 최대값이 큰 경우 → unordered_map으로 구현
- 대부분의 코테 문제는 경로 압축, 랭크 기반까지 구현할 필요는 없음
언제 집합 알고리즘을 쓸까?
이미지 세그멘테이션
- 각 이미지를 의미있는 부분으로 분할
네트워크 연결성 확인
- 대규모 네트워크에서 두 컴퓨터가 서로 연결되어 있는지 확인
집합
- 상호배타적 집합이란?
- 집합의 연산
- union 연산과 find 연산
- 경로 압축 / 랭크 기반 알고리즘으로 개선하기
- 집합의 구현
상호배타적 집합
- 교집합이 없는 집합관계(집합은 꼭 2개가 아니라 N개일 수도 있음)
집합 표현하기
무엇을 고려해야 할까?
- 특정 집합 원소들이 하나의 집합의 원소라는 것을 알 수 있어야 함.
- 집합 A = {1, 2, 3}일 때 각 원소가 집합 A에 속한다는 것을 알아야 함.
- 각 집합 간 다른 집합임을 알 수 있어야 함.
- 집합 A = {1, 2, 3}, ㅠ = {4, 5, 6}일 때 두 집합이 다른 집합임을 알아야 함.
- 특정 원소가 어느 집합에 속하는 지 알 수 있어야 함.
- 집합 A = {1, 2, 3}, B = {4, 5, 6}일 때 원소 5가 집합 B에 속함을 확인 가능해야 함.
- 두 개의 집합을 하나로 합칠 수 있어야 함.
- 집합 A = {1, 2, 3}, B = {4, 5, 6}일 때 이를 합쳐서 {1, 2, 3, 4, 5, 6}을 만들 수 있어야 함.
main idea - 각 집합의 대표 원소를 만들면 해결된다.
대표 원소
각 집합에서 가장 작은 원소를 대표원소(루트 노드)로 한다.
ex) 집합 A = {1, 2, 3}, B = {4, 5, 6}일 때 A의 대표 원소는 1, B의 대표 원소는 4
- 대표 원소는 현재 노드와 부모 노드가 같음
- 배열로 나타낼 수 있음(현재 노드는 인덱스, 부모 노드는 값)
- 부모 노드가 없다면 -1로 나타낼 수 있음
집합의 연산
find
특정 노드의 루트 노드를 확인하는 연산
- 특정 노드로부터, 루트 노드가 나올 때까지 거슬러 올라가면 됨
- union연산에서도 활용됨
find의 최악의 경우
- 루트 노드를 찾는데 필요한 경로가 길어질 경우 연산 횟수가 증가함 O(N)
- 어떻게 하면 경로의 깊이를 줄일 수 있을까?
- → 경로 압축 알고리즘 활용!
find 경로 압축
find 연산을 하는 노드가 루트 노드일 경우, 루트 노드 반환
find 연산 하는 노드가 루트 노드가 아닐 경우, 자신의 부모 노드를 find(해당 노드의 부모 노드)로 설정
union
두 개의 집합을 하나의 집합으로 합치는 연산
find 연산을 통해 각 집합의 대표 원소를 구하고 루트 노드를 하나로 통일
→ 여러 방법이 있지만 작은 루트 노드 쪽으로 합치는 방법도 있음
효율성에 대한 고민
union 연산 이후 깊이 최소화할 수 있을까?
→ 집합에 랭크를 도입하자!(특정 노드 기준 최대 높이)
→ 랭크가 더 큰 쪽으로 합쳐서, 랭크의 증가를 최소화하자(랭크 기반 알고리즘)
랭크 기반 알고리즘
집합의 구현
- 노드의 최대값이 크지 않은 경우 → 배열
- 노드의 최대값이 큰 경우 → unordered_map으로 구현
- 대부분의 코테 문제는 경로 압축, 랭크 기반까지 구현할 필요는 없음
언제 집합 알고리즘을 쓸까?
이미지 세그멘테이션
- 각 이미지를 의미있는 부분으로 분할
네트워크 연결성 확인
- 대규모 네트워크에서 두 컴퓨터가 서로 연결되어 있는지 확인