Algorithm - Greedy algorithm - huffman code & knapsack problem

문자를 코드로 나타내는 방법

• Fixed-length binary code

  • 코드의 길이가 고정되어 있다.
  • ex) a: 00, b:01, c:11

• Variable-length binary code

  • 코드의 길이가 가변적이다.
  • ex) a:10, b:0, c:11
  • a를 00으로 표기한다면 b와 구분할 수 없다는 문제가 발생한다.

• Optimal binary code

  • 주어진 파일에 있는 문자들을 이진코드로 표현하는데 필요한 비트의 개수가 최소가 되는 코드
    

• Prefix code

  • 한 문자의 코드워드가 다른 문자의 코드워드의 앞부분이 될 수 없다
  • 앞으로 읽을 비트를 확인하지 않아도 코드를 해석할 수 있다는 장점이 있다.
    

Huffman code

• optimal binary code이면서 prefix code

구축방법

• 문자의 빈도수를 데이터로 갖는 n개의 노드를 생성한다.
• 빈도수의 합이 최소가 되는 노드를 합병시켜 이진트리로 구축한다.
  모든 노드가 하나의 이진트리가 될 때까지 반복한다.
  

pseudo code

• priority queue를 사용하여 heap 구조를 통하여 구현한다.
  

0-1 knapsack problem

• 배낭에 넣을 수 있는 총 무게를 W라고 할 때 wi는 i번째 item의 무게이며 pi는 i번째 아이템의 가치를 나타낸다.
• W를 초과하지 않으면서 가장 많은 Value를 가방안에 담기 위한 문제

무작정 알고리즘식 접근 방법

• item의 개수가 n개일 때 각각의 아이템은 포함되거나 포함되지 않거나의 2가지 경우를 가진다.
• 따라서 총 2^n개의 부분집합을 계산하여야 하기에 비효율적이다.

탐욕적 알고리즘

• 가장 비싼 물건, 가장 가벼운 물건, 무게 가치당 가치가 높은 물건부터 넣는다고 하여도 최적의 해에 도달할 수 없다.
  

fractional knapsack problem

• 물건의 일부분을 잘라서 넣을 수 있다고 가정한다.
• 단위무게당 가치가 가장 큰 것부터 넣고 더이상 담을 수 없다면 배낭의 남은 무게만큼 물건을 잘서 넣는다.

동적계획식 접근 방법

• 전체 무게가 w를 넘지 않도록 i번째까지의 항목 중에서 얻어진 최고의 이익을 P[i][w]라고 한다면
  
• P[i-1][w]는 i번째 항목을 포함시키지 않은 경우의 최고 이익이며, pi + P[i-1][w-wi]는 i번째 항목을 포함시키는 경우의 최고 이익이다.

pseudo code