[알고리즘] Greedy strategy / 그리디 알고리즘 전략, 구성

그리디 알고리즘 구성하기

 

1. 문제의 최적의 부분구조를 만든다. (문제를 잘 이해하고 어떻게 해결할지 구성하라는 의미이다.)

2. 재귀적으로 해결책을 도출한다.

3. 재귀 내부의 어느 단계이든, 최적의 선택 중 하나는 반드시 greedy choice 임을 증명한다.

4. greedy choice 를 했을 때, 하나의 부분문제만 남는 것을 보인다. (계속해서 greedy choice를 해야되기 때문에)

5. 그리디 알고리즘을 완성시킨다.

6. 재귀적인 알고리즘을 iterative 하게 변환한다.  

 

* 재귀적인 알고리즘 -> iterative 알고리즘  과정을 거치는 이유는 생각하는데에 있어서 편하기 때문이지

  바로 알고리즘을 구현할 수 있다면 굳이 거치지 않아도 된다.

 

 

출처 : 고려대학교 정순영 교수님 알고리즘 수업,

introduction to algorithms 3rd edition - 토머스 H. 코르먼(Thomas H. Cormen) 찰스 E. 레이서슨(Charles E. Leiserson)