그리디 (Greedy)

특징#

• Greedy(탐욕적 기법) 닉값 충실한 방법 -> 눈앞의 이익을 그대로 좇는다
• 최적해를 보장하는지 확인하기 힘들다!

최적해와 최종해 >

> A에서 최종해(Global)을 구하려고 했을 때
-> Greedy를 사용한다면 m으로 향함
-> 최종해인지 아닌지 확인하기 힘들 뿐 더러
-> 최적해(local) 인지도 확신할 수 없다! (저 옆에 더 높은 m'가 있다면?)

• 그럼에도 특정한 경우에는 적용 가능한데..

조건#

• 문제의 크기(N)이 작고
• 문제의 성질이 동일하게 보존되고
• 같은 전략을 반복적으로 사용할 수 있는 경우

ex) 최소한의 동전으로 물건 값 계산하는 문제

• 500, 100, 50, 10, 큰 동전은 작은 동전의 배수
  => 작은 동전 여러개를 모아 큰 동전으로 바꾸면 무조건 동전 개수를 줄일 수 있다
  => 값이 큰 순서대로 동전을 최대로 사용하면 최적해를 구할 수 있음
  
  
• 위 조건이 성립하지 않는 경우 (60, 50, 10 짜리 동전) => 220원

1. 그리디: 60 X 3 + 10 X 4 = 7게
2. 최적해: 50 X 4 + 10 X 2 = 6개
   => 그리디로 해결하지 못함

적용#

• 그냥 구현하면 된다!
• 주로 N이 작은 문제에서 많이 사용된다는 것 알아두면 좋다!

문제#

[11047번: 동전 0]

업데이트 중…