그리디 알고리즘이란?

현재 상황에서 가장 좋아보이는 것만 선택하는 알고리즘

하지만 ‘최적 해’ 찾는 정당성을 고민하며 문제 해결방안을 떠올려야한다.

• 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘 포함

거스름돈

카운터에 거스름돈 500,100,50,10원 동전이 무한히 존재할 때 거슬러 줘야할 동전의 최소 개수를 구하라.

해결 아이디어

• 가장 큰 화폐부터 돈을 거슬러주는 것이 최적의 해를 보장하는 이유는?
  

동전의 가장 큰 단위가 항상 작은 단위의 배수이므로 작은 단위 동전들을 종합해 다른 해가 나올 수 없기 때문

아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.

n=1260
count=0
arr=[500,100,50,10] # 큰 단위부터 차례대로 확인하기
for i in arr:
		count+=n//i # 동전 개수 세기
		n%= i # 동전으로 원래돈을 나눈나머지로 계속해서 계산
print(count)