그리디 알고리즘

그리디 알고리즘

---

• '매 선택에서 현재 당장의 최적인 답'
• 백트래킹을 통해 추가 점검을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능 경우는 검증하지 않는다
• 

  

• 전체에서 최적 값을 언제나 구할 수 없다는 단점
  • 최초 선택에서 최적의 선택을 통해 **부분 최적해는 구했지만** **전체 문제에서는 최적값을 구하지 못함**
  • 최적해를 가지기 위해 다음 두 조건을 만족해야 한다
    1. 탐욕 선택 속성(Greedy Choice Property)
       • 이전에 선택이 이후에 영향을 주지 않음을 의미
    2. 최적 부분 구조(Optimal Substructure)
       • 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야 함을 의미
       • cf) [DP의 사용조건](https://hongjw1938.tistory.com/47)
  • 일반적으로 그리디임을 증명하려면 수학적 증명이 동반되어야 함
    • 반례를 1개만 찾아도 된다

 

• ex)거스름 돈 문제
  • 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해 보장하는 이유-> 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

n = 1260
count = 0

#큰 단위의 화폐뷰터 차례대로 확인
array = [500, 100, 50, 10]

for coin in array:
  count += n // coin # 해당 화폐로 거슬러 줄 수 있는 도전의 개수 세기
  n %= coin

print(count)