[Greedy]그리디 알고리즘

 

현재 상황에 지금 당장 좋은 것만 고르는 방법

그리디 알고리즘은 말 그대로 '탐욕스럽게' 매 순간 최선의 선택을 하는 기법이다.

현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않기 때문에, 최적해를 찾지 못하는 경우도 생긴다.

이런 단점을 극복하기 위해 가장 좋은 것만 선택하는 방식으로 문제를 풀 수 있는지 고려해야한다.

부분의 최선이 전체의 최선이 되지 못하는 예외 경우가 있는 지 판단하는 것이 관건이다.

 

 

그리디 알고리즘은 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다.

그러나 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에, 여러 유형과 섞여 출제된다.

 

일반적으로 그리디 알고리즘은 크기가 가장 큰 단위나 기준을 먼저 사용한다.

대표적으로 거스름돈 문제가 있다.