SSAMKO의 개발 이야기

그리디 알고리즘(greedy algorithm) - 동전 지불 문제¶ 그리디 알고리즘이란, 쉽게 말해 매 순간 최선의 선택을 하는 알고리즘이다. 전체의 최선이 아닌 매 순간의 최선이기 때문에 전체로 봤을 때는 최선이지 않은 경우가 종종 발생한다. 다시 말해 그리디 알고리즘에서는 2보 전진을 위한 1보 후퇴라는 말은 허용되지 않는다. 오로지 전진만 할 뿐이다. 그리디 알고리즘에 대해 좀 더 자세히 알고 싶다면, 나무위키 - 그리디 알고리즘을 참고하자 동전 지불 문제는 동전의 종류와 지불할 돈이 주어지면, 가장 적은 수의 동전을 사용해 비용을 지불하고, 그 때, 각 동전들이 몇 개 씩 사용되었는지, 잔돈이 생긴다면 잔돈까지 출력하는 코드를 짜는 것이다. 가장 큰 액수의 동전부터 사용해서 점차 작은 단위로 가..