1. 집합 (Set)
ㅇ 데이터를 수학적 집합의 요소로써 관리하는 자료구조
- 정렬되어있지 않고, 모두 유일함
- 즉, 중복값 허용 불가
ㅇ 집합 내 요소 접근 시간은,
- 빅오 표기법으로, O(1) 임
- 그 이유는, 해시 테이블의 구현을 기초로 하기 때문임
ㅇ 例) 자바스크립트의 Set 객체, 파이썬의 내장 자료구조인 집합 등
2. 딕셔너리 / 사전 (Dictionary) ☞ 연관 배열 참조
ㅇ 데이터를 키(Key)와 값(Value)의 쌍(Pair)으로 관리하는 자료구조 (key-value pair)
ㅇ 특징
- 탐색 키(또는, 연관 키)에 의해 식별되고 관리됨
. 키로 검색하고, 결과로 값을 반환
- 내용 변경, 크기 변경(늘임,줄임)이 쉬움
ㅇ 구현 필요 연산
- 삽입 (add) : add(key, value)
- 삭제 (delete) : delete(key)
- 탐색 (search) : search(key)
- 멤버십 여부 확인 등
ㅇ 例) 파이썬의 내장 자료구조인 사전 등
※ (비교)
- 리스트 : 키 보다는 주로 위치에 의해 관리됨
- 사전 : 모두 탐색 키에 의해 관리됨
3. 합 찾기 (Union Find), 병합 찾기 집합 (Merge Find Set)
ㅇ 서로소 집합들로 나누어진 원소들에 대한 정보를 저장 조작하는 자료구조
ㅇ 구현에 필요한 연산
- 초기화 또는 생성 : make-set(x), 상호배타적인 집합 생성 (원소 x로만 이루어진 집합)
- Union 연산 : union(x,y), 원소 x를 갖는 집합과 y를 갖는 집합을 하나로 합침
- Find 연산 : find-set(x), 원소 x를 갖는 집합을 찾음
ㅇ 구현용 자료구조 : 주로, 연결 리스트,트리 등을 이용
ㅇ 연결 리스트에 의한 구현
- 매 서로소 집합을 연결 리스트로 구현
- 각 원소 마다 2개 포인터로, 하나는 다음 원소, 또하나는 대표 원소를 가리킴
- 대표 원소는 맨 앞에 있는 원소로써,
. 1개 포인터는 자기자신을 가리킴
. 처음 생성시 즉,make-set(x) 경우에, 다음 원소에 대한 포인터는 NULL로 해둠
- 마지막 원소를 가리키는 tail 이라는 변수를 둠