[11주차] 11/17(월) 강의내용

Algorithm-10-Greedy

---

Algorithm-10-Greedy

 

GREEDY ALGORITHM

-> 해를 구하는 일련의 선택 과정마다

그 단계에서 ‘가장최선’ 이라고 여겨지는 국부적인 최적의 해를선택해나가면

결과적으로 전체적인 최적해를 구할 수 있을 것이라고 희망적인 전략을 취하는 방법

 

-> 동작과정

1. 해 선택

2. 실행 가능성 검사

3. 해 검사

 

최소 개수 거스름돈 만들기

1) Greedy

2) Dynaminc

 

KNAPSACK PROBLEM

-> 최대 용량 M인 하나의 배낭과 각각 무게wi와 이익bi가 부여되어 있는 n개의 물체가 있다고 가정

-> 배낭의 용량을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 물체를 집어넣는 방법을 찾아내는 것

 

1) FRACTIONAL KNAPSACK PROBLEM

2) 0/1 KNAPSACK PROBLEM

 

HUFFMAN CODING

1) Fixed Length Code

2) Variable Length Code

 

PREFIX FREE CODE