그리디(탐욕) 알고리즘
가장 좋은 것만 취한다는 의미에서의 그리디이다.
이전 결과를 신경쓰지 않고, 현재 상황에서 자신이 가진 최적 값과 입력된 값을 비교해 최적인 값을 취한다.
언제 사용하는가?
최적의 해(최대, 최소 등)를 구해야 하는 경우
주의할 점
항상 최적해를 도출하는가에 대한 주의를 해야 한다.
자주 등장하는 유형
순회하며 최적해 고르기
- 처음부터 끝까지 쭉 훑으며 비교해 최적해를 계속 갱신하는 방식
- 배열에서 최대/최소값 찾기가 이에 해당한다.
최적해를 도출할 공식을 정한 뒤 예외를 쳐 냄
- 항상 최적인 공식이 정해져 있고, 이를 최대한 많이 적용하는 방식
- 웬만한 난이도에서면 최적인 공식만을 적용할 수 없도록 예외가 존재한다.
- 이를 빠짐없이 찾아내는 것이 어려워 은근 정답률이 낮은 유형
- 최대/최소의 입력 조건, (반복문 등에서의) 최대/최소 조건을 잘 살펴야 함