[이코테]그리디(탐욕법)

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법(다만, 나중에 미칠 영향을 고려하지 않는다)
• 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야한다.

 

n = 1260
count = 0

coin = [500, 100, 50, 10]

for i in coin:
  count += n // i # 정수만 취함
  n %= i # 나머지
print(count)

 

• 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분한다.
• 하지만 거스름돈 문제에서 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것과 같이, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적.
• 그리디로 문제를 해결 했을 때 정당한지 검토하 해야함