Greedy 알고리즘이란

Greedy(탐욕, 탐욕법) 알고리즘

- 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여, 최종 해답에 도달하는 문제 해결 방식이다

- 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법으로, 각 단계에서의 최선의 선택이 전체적으로도 최선이길 바라는 알고리즘이다

- 따라서 모든 경우에서 통하지 않는다

 

maximum value 찾기에 실패한 greedy algorithm

- 이러한 단점을 극복하는 greedy의 가장 큰 장점은 계산 속도에 있다

- greedy 방법이 통하는 몇몇 문제에서는 최적해를 빠르게 산출해낼 수 있다

 

예시

활동 선택 문제

한 강의실에서 여러 개의 수업을 하려고 할 때, 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 것

 

 

- [A1, A3, A6, A8]이나 [A1, A3, A7, A9]를 고르면 정답

- 동적 프로그래밍을 통해서도 풀 수 있다

- 그리디 알고리즘으로 풀면, 최적의 해를 구하기 위해서는 활동이 최대한 일찍 끝나면 된다

  - [A1, A3, A6, A8]의 순서로 고르게 된다