Greedy Algorithm

<aside> 💡 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 문제 해결 방식

</aside>

실제 큰 수는 99지만, greedy하게 각 단계별로 큰 수를 구하면 12가 나올 수 있다.

즉, 전체 문제해결에서는 최적 해답을 찾지 못함

• 탐욕 알고리즘은 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달한다
• 그 순간의 선택은 그 당시(local)에는 최적이다. 그러나 최적이라고 생각했던 해답들을 모아서 최종적인(global)해답을 만들었다고 해서, 그 해답이 궁극적으로 최적이라는 보장이 없다.
• 따라서 탐욕 알고리즘은 항상 최적의 해답인지 검증이 필요하다.

장점 빠른 계산 속도

탐욕 알고리즘 설계 절차

1. 선정 과정

• 현재 상태에서 가장 좋을 것이라고 생각되는(greedy)해답을 찾아서 해답 모음(solution set)에 포함 시킨다

2. 적정성 점검 ex) 위의 c++ 동전 예시에서 거스름돈을 초과하면 선택하지 않는다.

• 새로 얻은 해답 모음이 적절한지결정한다.

3. 해답 점검

• 새로 얻은 해답 모음이 최적의 해 인지를 결정한다.

c++ 구현 예제