[Introduction to Algorithms] 그리디 알고리즘

1) 그리디 알고리즘이란?

- 최적화 문제를 위한 알고리즘들은 통상적으로 일련의 단계를 거치는데,

  각 단계마다 여러 가지 경우 중에서 선택을 해야 한다.

  최적화 문제에서 동적 프로그래밍을 사용하면 가장 좋은 선택을 결정하기 위해

  지나치게 많은 일을 하게 된다.

  오히려 더 간단하고 효율적인 알고리즘만으로도 충분한 경우가 많다.

 

- 그리디 알고리즘(Greedy Algorithm)은 항상 각 단계에 있어서 

  가장 좋을 거라 생각되는 선택을 한다.

  다시 말해 이 선택이 전체적으로 최적해로 안내하게 될 거라는 바람을 가지고

  부분적으로 최적인 선택을 한다. 

 

- 그리디 알고리즘은 언제나 최적의 해답을 구하지는 못하지만 

  많은 문제에 대한 해를 구해줄 수 있다. 

  우선, 활동 선택 문제(activity-selection problem)은 

  그리디 알고리즘이 효율적으로 해를 계산해낼 수 있는 문제다. 

  먼저 동적 프로그래밍 방법을 고찰해본 후 

  최적해에 도달하기 위해 항상 그리디 선택을 해도 된다는 것을 보일 것이다. 

 

- 그리디 알고리즘이 정확한 해를 찾음을 증명하는데 있어 

  직접적인 방법을 제공하는 그리디 방법의 기본 구성요소가 존재한다.

  또한, 그리디 방법의 중요한 응용인 데이터 압축(허프만 코드)과

  항상 최적해를 생성하는 매트로이드(matroid)라 불리는 조합 구조에 기초를 둔

  이론의 일부가 존재한다. 

 

- 그리디 방법은 아주 강력해서 광범위한 문제에 적용된다.

  그리디 방법은 최소 신장 트리(minimum-spanning-tree) 알고리즘,

  한 개의 시작점으로부터의 가장 빠른 경로를 구하는 다익스트라 알고리즘

  등에 응용된다.