[PCCP] 자료구조 - 집합

1. 이론

- 집합(set): 순서와 중복이 없는 원소를 갖는 자료구조

- 집합 종류: 유한집합, 무한집합, 공집합, 상호배타적 집합

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

- 상호배타적 집합 활용분야: 이미지 분할, 도로네트워크 교차로, 최소신장트리의 사이클 확인, 게임개발시 물체 충돌 문제, 클러스터링 방지

- 집합의 연산: 합치기, 탐색

- 집합 표현: 배열을 활용한 트리 사용. 배열의 인덱스는 자신, 배열값은 부모 노드를 의미. 루트노드는 인덱스와 값이 동일

- 루트 노드의 개수는 집합의 개수

- Union-Find 알고리즘: union(합치기), find(탐색).

- find 연산: 특정 노드의 루트 노드가 무엇인지 탐색하는 방법. 특정 노드가 같은 집합인지 확인. 재귀로 구현

+) find 연산 비용은 경로 압축으로 해결: 배열값을 부모 노드가 아닌 루트 노드로 변환. 트리의 깊이가 달라짐

- union 연산: 두 집합을 하나로 합치는 연산. 두 집합의 루트노드를 동일하게 변경

+) union 연산 비용은 랭크로 해결: 깊을수록 연산 비용이 커지는 문제를 랭크가 큰 루트 노드를 작은 루트 노드의 부모로 사용

+) Rank: 현재 노드를 기준으로 가장 깊은 노드까지의 경로 길이

- 집합 ADT: 

 

(시간복잡도)

- 임의 접근:

- 삽입:

- 삭제:

 

(선택시 고려할 점)

- 

- 

 

 

2. 프로그램 언어별 문법

- 집합 선언 및 초기화

- 집합 접근: 

- 집합 제어: 삽입, 삭제

 

<C언어>

 

<C++>

- 정렬된 집합: 트리 구조

#include <set>

/* 선언 및 초기화 */
std::set<자료형> s;

/* 삽입 */


/* 삭제 */


/* 변경 */


/* 조회 */


/* 전체 조회 */


/* 기타 메서드 */

- 정렬되지 않은 집합: 해시 구조

#include <unordered_set>

/* 선언 및 초기화 */
std::unordered_set<자료형> us;

/* 삽입 */


/* 삭제 */


/* 변경 */


/* 조회 */


/* 전체 조회 */


/* 기타 메서드 */

 

<C#>

- 정렬된 집합

/* 선언 및 초기화 */
SortedSet<자료형> ss = new SortedSet<자료형>(); 

/* 삽입 */
ss.Add(값);

/* 삭제 */


/* 변경 */


/* 조회 */


/* 전체 조회 */


/* 기타 메서드 */

- 정렬되지 않은 집합

/* 선언 및 초기화 */
HashSet<자료형> hs = new HashSet<자료형>();

/* 삽입 */
hs.Add(값);

/* 삭제 */


/* 변경 */


/* 조회 */


/* 전체 조회 */


/* 기타 메서드 */

 

<Java>

 

<Python>

 

<JavaScript>

 

 

 

3. 추천 문제

(프로그래머스)

- Lv 1: 폰켓몬(1845) / 폰켓몬(1845) 해설

- Lv 2: 영어 끝말잇기(12981) / 영어 끝말잇기(12981) 해설 (Java/JS만. 나머지는 해시)
- Lv 2: 전화번호 목록(42577) / 전화번호 목록(42577) 해설 (JS만. 나머지는 해시)

- Lv 3: 섬 연결하기(42861) / 섬 연결하기(42861) 해설

 

(leetcode)

-