[알고리즘] 그리디 / greedy

지금 당장 좋은 것 고르기

 

 

문제 알아보기

1. 가장 큰 순서대로, 가장 작은 순서대로와 같이 기준을 알게 모르게 제시해준다.

-> 대체로 이 기준은 정렬 알고리즘을 사용해 만족시킬 수 있으므로 정렬 알고리즘과 같이 짝지어 출제되는 경우가 많다. 

 

2. 그리디로 풀 수 있는 문제인지 파악하기

-> 미리 알고리즘을 간단히 계획해보고 그리디로 풀었을 때 최적해를 반환하는지 판단해야 한다. 

 

3. 현재 선택이 이후의 선택에 영향을 주지 않는다.

 

4. 매 순간 최적의 해가 문제 전체의 최적의 해이다. 

 

특징 

계산속도가 빠르고 풀이가 간단하다 -> 제한 시간이 짧고 조건이 성립할 때 유용