| 그리디 알고리즘 개념 | 그리디를 활용한 문제 |

■ 알고리즘 설계 기법

• 간단히 효율적인 알고리즘을 구할 수 있는 경우도 있지만 많은 경우 주어진 문제를 해결하는 알고리즘을 찾는 일이 쉽지 않은 경우가 대부분이다.
• 일반적으로 알려져 있지 않은 새로운 알고리즘을 설계하기 위해서는 여러가지 기법을 동원하게 된다.  단순히 직감적으로 해를 알 수 있는 경우에는 직접 구현하겠지만 대개의 경우 그렇게 하기는 거의 불가능하고, 설사 가능하다 하더라도 구현에 있어서는 비효율적이기가 일쑤이다.
• 일반적으로 적용가능한 알고리즘 설계 기법도 많지는 않으나 비교적 단순하면서도 널리 사용가능한 기법으로 그리디방법(Greedy method), 분할 정복(Divide and conquer) 그리고 동적 프로그래밍(Dynamic programming)과 선형 프로그래밍(Linear programming)등이 있다.

■ 그리디(Greedy) 알고리즘 개념

• 설계 기본방침은 선택할 것이 여러 개일 경우 그 중 가장 좋은 것을 취한다는 것 - 욕심쟁이 방법
• 문제가 여러 단계로 구성되어 각 단계별로 최적해를 구함
• 전체적 최적화보다 단계별 부분적(지역적, local) 최적화 구함
• (예) 물건을 사고 거스름돈을 내주는 것 - 큰 단위의 잔돈 계산함
• 정확한 알고리즘보다 빠른 단계적 최적화를 구할 때 사용
• 가장 간단한 설계방법이고, 좀더 다양한 문제들에 적용할 수 있음
• 단점 : 단계별로 진행되어 각 단계에서는 현재 상태에서 가장 최적이라고 판단되는 결정을 내린다. 이 때 전체적으로 최적인지 여부는 검사하지 않고 현재 상태의 입장에서만 보았을 때 가장 최적이라고 판단되는 결정을 내린다. 즉 그리디 알고리즘은 문제에 따라 최적해를 구할 수 있고,
  그렇지 않을 수도 있다.
• Dijkstra의 Shortest Path Algorithm(최단경로알고리즘) 이나 MST(Menium Spaning Tree = 최소비용트리) 같은 유명한 알고리즘들은 모두 그리디를 이용한 알고리즘