경일 메타버스 20220706 14주차 3일 수업내용. 자료구조와 알고리즘 - 힙, 해시 테이블

힙(heap)

• 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조.

  • 최대 힙 (Max heap) :
    키값이 가장 큰 노드를 찾기 위한 힙

  • 최소 힙(min heap) :
    키값이 가장 작은 노드를 찾기 위한 힙

• 우선순위 큐(priority queue)라고도 한다.

STL에서의 구현

• std::priority_queue : https://en.cppreference.com/w/cpp/container/priority_queue

• C++ : 최대 힙

• C# : 최소 힙

힙의 불변성

1. 힙은 최대 / 최소 원소에 즉각적으로 접근이 가능해야 한다.

• 따라서 최대 / 최소 원소가 항상 고정된 위치에 있어야 한다.

2. 최대 / 최소 원소는 항상 트리의 루트에 존재한다.

3. 부모 노드가 두 자식 노드보다 항상 크거나 작아야 한다.

연산

• 검색 및 읽기
  최대 / 최소 원소에 대해서만 가능하며 O(1)이다.

• 삽입
  완전 이진 트리이기 때문에 O(logN)이다.

• 삭제
  최대 / 최소 원소에 대해서만 가능하며 O(logN)이다.

• 힙의 경우는 낭비되는 메모리가 거의 없기 때문에, 배열로 구현한다.

해시 테이블(Hash table)

• 빠른 검색을 위한 자료구조.

• 해싱을 활용해 데이터를 저장하는 검색을 위한 자료구조.

• 연관 배열(associative array)

• 배열처럼 사용할 수 있다.

• 해시 값을 테이블의 인덱스로 활용한다.

• 해시 알고리즘 :
  SHA 알고리즘
  SHA-128 / SHA-256 / SHA-512

• STL에서의 구현
  • std::undordered_set :
    https://en.cppreference.com/w/cpp/container/unordered_set
  • std::undordered_map :
    https://en.cppreference.com/w/cpp/container/unordered_map
  • std::undordered_multiset :
    https://en.cppreference.com/w/cpp/container/unordered_multiset
  • std::undordered_multimap :
    https://en.cppreference.com/w/cpp/container/unordered_multimap

• 해싱(Hashing)과 선형 리스트의 성질을 이용

  1. 선형 리스트의 읽기 연산은 O(1)이다.

  2. 해싱으로 인덱스를 구한다.

해싱(hashing)

• 입력의 크기에 상관 없이 일정 크기의 값으로 변환하는 것.

• 어떤 입력이 주어지든 고정된 길이의 출력으로 바꾸는 것.

  • 이에 사용되는 함수를 해시 함수(hash function)라 한다.

1. 균일성 :
   충돌이 적은 것을 의미한다.

   • 충돌(collision) :
     서로 다른 값이 같은 해시 값을 생성한 것

2. 효율성 :
   계산하기 쉬워야 한다.

3. 결정적 :
   같은 입력에는 같은 값을 내놓아야 한다.

• std::hash
  해싱을 실행하는 함수

연산

• 특정 키를 알고 있을 때의 연산

  • 읽기
    O(1)이다.

  • 검색 : 특정 키에 대한 데이터의 검색
    O(1)이다.

  • 삽입
    O(1)이다.

  • 삭제
    O(1)이다.

이진 검색 (트리) 와의 비교, 선택

• 항상 정렬이 필요한 데이터 ⇒ 이진 검색

• 그렇지 않다면 ⇒ 해시 테이블

  • 해시 테이블은 정렬이 불가

충돌 처리

• 선형 개방 주소법 or 선형 조사법

  • 충돌이 나면 빈 곳을 찾아서 넣는다.

• 체이닝

  • 충돌이 나면 리스트로 충돌이 난 여러 해시 값을 저장하게 한다.