그리디 알고리즘

1. 정의 

매 순간 최적이라고 생각되는 것을 선택하여 최적 해에 도달하는 기법. 

2. 속성 

- greedy choice propoerty   :  앞의 선택이 이후에 영향을 주지 않음 .

- optimal substructure         :  문제 전체에 대한 최적 해가 부분 문제에서도 최적 해를 만족해야 함. 

3. 대표 예제 

 

1)  분할 가능한 배낭 문제 ( Fractional knapsack problem ) 

     풀이 방법 :  단위 무게당 값어치가 가장 큰 것 부터 가방에 넣는다. 

                        <--> Dynamic Programming의 '0-1 Knapsack Problem)이랑 차이! 

2)  교실 할당 문제 ( Activity-Selection Problem )  : 한정된 교실 내에 최대 수업을 배정하자. 

     풀이 방법 : 종료 시간이 가장 빠른 수업을 배치하고 이와 겹치지 않는 나머지 수업을 배치함. (  O(n)  ) 

3)  Huffman Coding :  그리디 알고리즘을 사용해서 데이터를 압축하는 기법. 

     풀이 방법 : 문자가 나오는 빈도에 따라 암호화 비트 수를 달리한다. 높은 빈도의 문자열은 짦게, 낮은 빈도의 문자열은 길게. 

                      문자열이 길 수록 더욱 압축률이 좋다. ( O(nlogn)  )