Dog foot print

서문 알고리즘 수업이 생각보다 난이도있게 흘러가고, 양방향 수업 부재로 인한 질의 응답이 어려워서 간단한 알고리즘들은 직접 구현해보며 만들어가는 것이 좋을 듯 생각이 들었다. 물론 꾸준히 업데이트 할 수 있을지는 미지수이지만 할만하다 싶은 부분들은 새롭게 올리는 것이 괜찮을 듯 싶다. 알고리즘 동전교환 알고리즘은 Greedy 알고리즘을 사용하여, 순간 순간 최적의 해를 선택하여 문제를 해결하는 방법이다. 여기서 문제란 현재 주어야 하는 잔돈에서 내가 어떤 조합으로 잔돈을 거슬러 줄 것인가이다. 그럼 여기서 순간순간 최적의 해란 ? 각 화폐 및 동전마다 최소의 수량을 결정하는 것이다. 우리가 약 95420원의 잔돈을 손님에게 전달해준다고 가정하자. 우리는 먼저 가장 큰 화폐권부터 계산을 할 것이다. 한국의..