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

(2022-11-08)

Union Find, Merge Find Set


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

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


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"