[알고리즘] Hash Tables & Dynamic Programming

Direct Addressing Table

• |U| 개의 slot으로 이루어진 Table T
  • U : 전체 집합
  • 가정 : 서로 다른 원소는 동일한 key를 갖지 않는다
• 수행 시간 : O(1)
• 메모리 공간 소비 상당
• U의 크기가 매우 크기 때문에, |U|개의 원소를 담을 수 있는 Table T를 이용하는 것은 실용적이지 못함
  • 컴퓨터 메모리의 함계
• 실제로 이용하고 있는 key들의 집합을 K라고 했을때, |K|는 |U|에 비해 매우 작음
  • Table T에 할당된 메모리 공간의 낭비가 매우 심함

Hash Table

#### Hash Function
- 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
    - 해시 함수에 의해 얻어지는 값 : 해시 값, 해시 코드 , 해시 체크섬, 해시
    - 해시 테이블에 사용 : 매우 빠른 데이터 검색 가능
    - 전송된 데이터의 무결성을 확인해주는 데 사용

- 해시함수의 평가
    - 해시 함수가 저장될 키 값들을 m개의 슬롯에 얼마나 잘 분배하는지 척도로 평가

- 좋은 해시 함수
    - 해시 함수는 deterministic하므로 현실에서는 키들이 랜덤하지 않음
    - Key들의 통계적 분포에 대해 알고 있다면, 이를 이용해서 해시 함수는 고안하는 것이 가능함
    - Simple Uniform Hashing Assumption(SUHA)를 만족하는 함수
            - 각 키가 모든 slot들에 균등한 확률로 (equally likely) 해싱 됨
            - 각 키ㅣ는 독립적으로 해싱 됨
    - 키들이 규칙(패턴)을 가지고 있더라도, 해시 값이 불규칙적으로 나오는 것이 바람직하다
        - 해시 값이 키의 특정 부분에 의해 결정되면 안된다.
- Revisit : Division Method
- Multiplication Method

• 해시 함수를 사용하여 키(key)를 값(value)으로 매핑(mapping)하며, 해당 값을 배열의 색인(index)로 이용하여 버킷(bucket)이나 슬롯(slot)에 접근하는 자료구조
• 원소가 저장된 자리가 원소의 값에 의해 결정되는 자료구조
• 해시 테이블, 해시 맵, 해시 표
• Direct Addressing
  • key k를 갖는 원소는 slot k에 저장
• Hashing
  • key k를 갖는 원소는 slot h(k)에 저장
  • h는 해시 함수
    • h: U -> {0,1,...,m-1} // U는 가능한 모든 key들의 집합,m은 Table의 크기
    • h(k)는 key k의 해시 값
  • "Key k가 h(k)로 해싱(Hashing)되었다"고 표현

Collision

• 충돌 문제
  • 서로 다른 두키에 대해 h(k1) = h(k2)인 상황
  • 두개 이상의 키가 동일한 slot에 해싱되는 상황
• 해결
  • "좋은 해시 함수"를 이용하여 충돌 최소화
    • 좋은 해시 함수 : 충돌나도 slot내에 원소 개수가 비슷한 것이 좋음
  • 충돌 회피는 불가능
    • 동일한 해시 값을 갖는 두개의 키가 존재할 수 밖에 없다
  • 충돌 해결
    • Chaining
    • Open Addressing

Chaing(=linked list)

• 연결 리스트를 이용하여 동일한 해시 값을 갖는 원소(혹은 key)를 관리
• slot j는 j로 해싱된 모든 원소들을 지니고 있는 연결 리스트의 HEAD를 가리키고 있음
• Insertion 동작의 수행 시간 : O(1)
  • 단, 중복된 키가 들어올 수 있고, 중복 저장이 허용되지 않는다면 삽입시 리스트를 검색해야 함
  • 수행 시간 : O(n) (n은 리스트 길이)
• Search 동작의 수행 시간 : O(n)
  • 최악의 경우 : 모든 key가 동일한 slot에 해싱되었을 경우 -> 단순 연결 리스트
• Deletion 동작의 수행 시간 : O(1)
• load factor
  • 각 체인의 평균 길이 ( 각 체인에 저장된 원소의 평균 개수 )
  • a = n/m
    • n: 테이블에 저장된 원소의 개수
    • m: 테이블의 크기(테이블에 저장된 원소의 수)
  • ex) 40개를 저장하고 싶을 때, 테이블 크기가 4
    • 답 : load factor = 8

Open Addressing

- 개방 주소 방법
    - 모든 원소는 해시 테이블 자체에 직접 저장
        - 체이닝처럼, 테이블 밖에 원소를 저장하는 리스트 필요 없다
        - 충돌이 일어나더라도 주어진 테이블 공간에서 해결한다
        - 해시 테이블의 각 slot에는 1개의 원소만 저장한다 --> lad factor = 1
- 대표적인 기법
    - 선형 조사
    - 이차원 조사
    - 더블 해싱
- Insertion
    - Empty slot을 찾을 때까지, 해시 테이블을 검색/조사 (probe) 후 삽입
        - 빈자리가 생길 때까지 해시값을 계속 만들어냄
        - 키의 저장 상태에 따라, 검색/조사하는 위치와 순서 달라짐
    - m! 검색/조사 순서(Probe sequence)존재

< Hash-Insert(T,k) >

i <- 0
repeat j <- h(k,i)
        if T[j] = NIL
            then T[j] <- k
                return j
        else i <- i + 1
    until i = m
error "hash table overflow"

• Search
  < Hash-Search(T,k) >
• i <- 0 retpeat j <- h(k,i) if T[j] = k then return j i <- i + 1 until T[j] = NIL or i = m return NIL
• Deletion
• Linear probing
  • 선형의 관계를 가지고 i증가, k 유지
• 1차 군집
  • Cluster : 키에 의해 채워진 연속된 slot의 집합
  • Search Time 길어짐
  • Cluster가 점점 더 커지는 경향이 있음
  • 군집이 클수록 찾아야하는 데이터 증가
• Quadratic probing
• 2차 군집
  • 여러 개의 원소가 동일한 키값을 가지는 경우
• Double Hashing
  • 처음 해시함수로는 해시값을 찾기 위해 사용하고 두번째 해시함수는 충돌 발생 시 탐사폭 계산 위해 사용
• Open Addressing에서는 키를 삭제할 경우 문제가 발생한다
  • Linear probing으로 충돌을 해결한다

동적 프로그래밍

• 적용 조건
  • 최적 부분구조
    • 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함됨
  • 재귀호출시 중복
    • 재귀적 해법으로 풀면 같은 문제에 대한 재귀 호출이 심하게 중복됨

< 피보나치 수열 : 재귀적 표현 >

int fib(int n)
{
 if ( n==1 || n==2 )
     return 1;
 else
     return fib(n-2) + fib(n-1);
}

< 하향식 접근법(Top-Down) >

int fib(int n)
{
    if (n==1 || n==2)
        return 1;
    else if (f[n] > -1) #배열 f가 -1으로 초기화되어 있다고 가정
        return f[n];
    else{
        f[n] = fib(n-2) + fib(n-1);
        return f[n];
    }    
}

< 상향식 접근법 (Bottom-Up)>

int fib(int n)
{
    f[1] = f[2] = 1;
    for(int i = 3; i<=n; i++)
        f[i] = f[i-1] + f[i-2];
    return f[n];
}

< 이항 계수 >

• 파스칼의 삼각형 : 이항계수를 삼각형 모양으로 나열 한 것

  int binomial(int n, int k)
  {
    if (n == k || k == 0)
        return 1;
    else
        return binomial(n - 1, k) + binomial(n - 1, k - 1);
  }

<하향식 접근법 (Top-Down)

int binomial (int n, int k)
{
    if ( n == k || k == 0)
        return 1;
    else if (binom[n][k] > -1) #배열 binom이 -1로 초기화되어 있다고 가정
        treutn binom[n][k];
    else{
        binom[n][k] = binomial(n-1,k) + binomial(n-1,k-1);
        return binom[n][k];
    }
}

<상향식 접근법 (Bottom-Up)>

int binomial(int n, int k)
{
    for (int i = 0; i<= n; i++){
        for(int j=0; j<=k && j<=i; j++){
            if (k==0 || n==k)
                binom[i][j] = 1;
            else
                binom[i][j] = binom[i-1][j-1] + binom[i-1][j];
        }
    }
    return binom[n][k];
}