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. 기타 자료구조(집합,딕셔너리 등)
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
            1. 자료구조
            2. 자료구조 종류
        1.   선형 자료구조 (리스트 등)
        2.   비선형 자료구조 (트리,그래프)
        3.   기타 자료구조
          1.   1. 기타 자료구조(집합,딕셔너리 등)
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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