Set, Dictionary   집합, 사전, 딕셔너리

(2020-03-17)
1. 집합 (Set)집합 요소는,
     - 정렬되어있지 않고, 모두 유일함
     - 즉, 중복값 허용 불가

  ㅇ 집합 내 요소 접근 시간은, 
     - 빅오 표기법으로, O(1) 임
     - 그 이유는, 해시 테이블의 구현을 기초로 하기 때문임

  ㅇ 例) 자바스크립트Set 객체, 파이썬의 내장 자료구조집합
2. 딕셔너리/사전 (Dictionary)데이터키(Key)와 값(Value)의 쌍(Pair)으로 저장하는 자료구조 (key-value pair)

  ㅇ 특징
     - 키로 검색하고, 결과로 값을 반환
     - 내용 변경, 크기 변경(늘임,줄임)이 쉬움


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 이라는 변수를 둠


[기타 자료구조] 1. 기타 자료구조(집합,딕셔너리 등)

 
        최근수정     요약목록     참고문헌