-1) 집합과 상호배타적 집합으 개념
집합은 순서와 중복이 없는 원소들을 갖는 자료구조
{1,6,6,6,4,3}은 집합으로 생각할 때 중복을 제외해서 {1,6,4,3} ( 순서 바껴도 됨 )
집합의 종류
- 유한집합 : 원소 개수가 유한한 경우
- 무한집합 : 원소 개수가 무한한 경우
- 공집합 : 아무런 원소도 없는 경우
이 책에서는 상호배타적 집합에 집중할 것!
상호배타적 집합
앞으로 나올 내용에서 집합이라고 말하는 것은 상호배타적 집합 의미
상호배타적 집합 : 교집합이 없는 집합 관계
( 여러개의 집합에 공통된 원소가 없는 경우 )
상호배타적 집합의 특성을 활용하는 분야
코딩테스트에서 이 집합을 배워야 하는 이유는 그래프 알고리즘, 특히 사이클을 확인할 때에서 많이 활용하기 때문 !
외에도 이미지 분할, 최소 신장 트리 알고리즘 등에 사용
-2) 집합의 연산
보통 집합은 트리로 표현하며 대표적인 연산에는 합치기와 탐색이 있음
배열을 활용한 트리로 집합 표현하기
집합은 배열을 활용한 트리로 구현
대표 원소
대표 원소는 집합의 원소 중 집합을 대표하는 역할
집합의 형태를 트리로 표현할 것이므로 이후 대표 원소는 루트 노드라고 부를 것
배열로 집합을 표현하는 것?
집합을 배열로 표현한다는 것은 하나의 배열로 상호 배타적 관계를 가지는 집합을 모두 표현한다는 것 의미
집합을 트리 형태로 표현할 때 다음만 기억하면 됨
- 배열의 인덱스는 자신을, 배열값은 부모 노드를 의미한다 !
예를 들어 disjoint_set[3]=9이면 노드 3의 부모 노드는 9임을 의미
루트 노드는 부모 노드가 없고 부모 노드가 자기 자신이므로, 루트 노드는 값 자체가 배열의 인덱스와 동일
배열의 크기는 배열의 인덱스가 모든 집합의 원소를 표현할 수 있으면 됨 ( 0 빼고 표현해야 )
집합의 개수는 루트 노드의 개수를 보면 됨 ! 즉, 배열의 인덱스와 값이 같은 경우가 몇번인지 확인
유니온 파인드 알고리즘
집합 알고리즘에 주로 쓰이는 연산은 합치기 (유니온)와 탐색 (파인드)
1. 파인드 연산
파인드 연산은 특정 노드의 루트 노드가 무엇인지 탐색하는 방법
-> 보통 특정 노드가 같은 집합에 있는지 확인할 때 사용
- 현재 노드의 부모 노드를 확인한다
부모 노드를 확인하다가 부모 노드가 루트 노드이면 찾기 연산을 종료한다 - 1에서 찾기 연산이 종료되지 않으면 1을 반복한다
-> 재귀 함수로 구현!
루트 노드를 현재노드와 부모노드가 같을때까지 재귀함수를 실행해 최종값을 반환하면 됨
파인드 연산의 목표는 루트 노드 찾기이지 부모 노드 찾기가 아님
더 효율적인 방법은 없을까?
파인드 연산의 연산 비용 문제, 경로 압축으로 해결하자
집합 형태를 유지하면서도 트리 높이를 줄이면 됨
2. 합치기 연산
두 집합을 하나로 합치는 연산 즉, 두 집합의 루트 노드를 같게 한다
1. 두 집합에서 찾기 연산을 통해 루트 노드를 찾는다
2. 찾은 두 루트 노드의 값을 비교한다
3. 두 집합의 루트 노드를 같게 해서 집합을 합친다
이때 루트 노드는 두 집합 중 어떤 루트 노드로 해도 상관없음
합치기 연산의 연산 비용 문제, 랭크로 해결하자
트리의 깊이가 깊어지면 깊어질수록 연산 비용이 커진다는 단점이 있음
랭크란?
랭크란 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이를 말함
- 두 노드의 루트 노드를 구한다
- 1에서 구한 루트 노드의 랭크를 비교한다
2-1. 랭크값이 다르면 랭크값이 큰 루트 노드를 기준으로 삼는다
즉, 랭크가 더 큰 루트 노드를 랭크가 작은 루트 노드의 부모 노드로 바꾼다 ( 이때 트리의 깊이는 더 깊어지지 않으므로 랭크의 값은 바뀌지 않음 )
2-2. 랭크값이 같으면 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더한다
