Greedy

그리디(탐욕) 알고리즘

가장 좋은 것만 취한다는 의미에서 그리디이다.

언제 사용하는가?

최적의 해(최대, 최소 등)를 구해야 하는 경우

주의할 점

항상 최적해를 도출하는가에 대한 주의를 해야 한다.

예시 - 거스름돈

500원, 100원, 50원, 10원을 통해 거슬러 줘야 할 최소 동전의 개수는?

금액이 큰 동전이 많을 수록 동전 개수가 작아지므로

총 금액에서 500원부터 10원까지 빼 가며 구하면 된다.

만약 동전의 조합이 500원, 400원, 100원이었다면 800원에 대하여 500원 + 100원 * 3 보다 400원 * 2가 효율적이므로 그리디를 적용할 수 없게 된다.

자주 등장하는 유형

순회하며 최적해 고르기

• 처음부터 끝까지 쭉 훑으며 비교해 최적해를 계속 갱신하는 방식

• 배열에서 최대/최소값 찾기가 이에 해당한다.

최적해를 도출할 공식을 정한 뒤 예외를 쳐 냄

• 항상 최적인 공식이 정해져 있고, 이를 최대한 많이 적용하는 방식

• 웬만한 난이도에서면 최적인 공식만을 적용할 수 없도록 예외가 존재한다.

  • 이를 빠짐없이 찾아내는 것이 어려워 은근 정답률이 낮은 유형

  • 최대/최소의 입력 조건, (반복문 등에서의) 최대/최소 조건을 잘 살펴야 함

• 예시) 들어오는 수를 더하거나 곱해 최대 값 만들기

  • 항상 최적인 공식이 곱셈이고 0과 1(예외)일 때는 더해야 한다.