1. 집합과 상호배타적 집합의 개념
집합의 개념
집합은 순서와 중복이 없는 원소들을 갖는 자료 구조.
ex)
A그룹 = {1,6,6,6,4,3} 이면 집합은 {1,6,4,3} or {6,1,3,4} or {3,6,1,4} ...등등
중복 제거, 순서 상관 X
집합의 종류
상호배타적 집합 : 교집합이 없는 집합 관계
2. 집합의 연산
배열을 활용한 트리로 집합 표현하기
집합은 배열을 활용한 트리로 구현.
대표원소란?
집합의 원소 중 집합을 대표하는 역할.
트리로 표현할 때는 루트 노드
배열로 집합을 표현하는 것이란?
하나의 배열로 상호 배타적 관계를 가지는 집합을 모두 표현한다
즉 2개의 집합(교집합이 없는)을 1개 배열로 다 나타내는 방법.
배열의 인덱스는 자신을, 값은 부모 노드를 의미
이때 배열의 크기는 반드시 가장 큰 원소(여기서는 9)에 +1 한만큼 잡아야한다
집합 표현 완벽 정리하기
위의 집합 A , B를 배열로 실제 구현할 때
1. 여기서는 가장 큰 노드가 9인데 배열의 크기를 9로 잡았다.
(이 부분이 크게 상관없는듯하다.)
2. 각 인덱스 값을 우선 자기 자신으로 초기화(만약 없는 원소의 인덱스를 -1로 초기화)
집합 A의 경우 9→3 →2 →1
이 순서 이동
유니온-파인드 알고리즘
집합 알고리즘에 주로 쓰이는 연산은 합치기와 탐색.
합치기 = union
탐색 = find
파인드 연산
특정 노드의 루트 노드가 무엇인지 탐색하는 방법.
특정 노드가 같은 집합에 있는지 확인하는 데 사용.
ex) A,B 두 노드가 있는데 이 노드의 루트 노드가 서로 같다면,
이 두 원소는 같은 집합에 속함. 보통 재귀로 찾음
1. 현재 노드의 부모 노드 확인.
2. 부모 노드가 루트 노드면, 연산 종료
3. 부모 노드가 루트 노드 아니면, 1 반복
파인드 연산의 연산 비용 문제, 경로 압축으로 해결
합치기 연산
두 집합을 하나로 합치는 연산.
Meaning? 두 집합의 루트노드를 같게 즉, 한쪽이 다른 한쪽에 속하는 방식.
1. 두 집합에서 찾기 연산을 통해 루트노드 찾는다.
2. 찾은 두 루트 노드의 값을 비교
3. 다르다
3-1 높이가 같다
- 한쪽 루트 노드를 다른 쪽 루트 노드의 바로 아래에 붙인다.
3-2 높이가 다르다
- 랭크 값이 큰(높이가 큰) 루트 노드가 전체의 루트노드가 되어
랭크 값이 작은 집합의 루트 노드를 큰 집합의 루트 노드의 자식 노드로 붙힌다.
끝!
♬ 자료 출처 - 책
코딩 테스트 합격자 되기 - 파이썬 편
이 포스팅의 모든 내용은 해당 책의 내용을 바탕으로 하고 있습니다.
감사합니다.
'프로그래밍 이야기 > 파이썬 코딩 테스트 스터디' 카테고리의 다른 글
| 파이썬 코딩테스트 스터디 7주차 #3 - 포켓몬 - 합격자가 되는 모의 테스트 (0) | 2024.08.09 |
|---|---|
| 파이썬 코딩테스트 스터디 7주차 #2 - 몸풀기 문제 : 간단한 유니온 - 파인드 알고리즘 구현하기 (0) | 2024.08.09 |
| 파이썬 코딩테스트 스터디 6주차 #5 - 다단계 칫솔 판매 (0) | 2024.08.04 |
| 파이썬 코딩테스트 스터디 6주차 #4 - 예상대진표 (3) | 2024.07.23 |
| 파이썬 코딩테스트 스터디 6주차 #3 - 이진 탐색 트리 구현 (1) | 2024.07.22 |