[알고리즘][다이나믹(동적 계획법)] 동전 교환 (정올)

다이나믹 (동적 계획법) 알고리즘 : 동전 교환 문제 (정올)

다이나믹 알고리즘의 가장 대표적인 문제가 아닌가 한다.

차곡차곡 저장된 데이터를 기반으로 답을 찾아간다는

단순한 논리이지만 수학문제를 푸는 것 같아 굉장히 어렵다..

이번 문제는 1시간 이상 걸렸고, 데이터를 차곡차곡

저장하는 방법과, 저장된 데이터를 빼서 사용하는

부분에서 상당히 애를 먹었다. ( 그냥 다 어려웠다는 말 )

01. 다이나믹(동적 계획법)을 수행할 클래스 선언

02. 초기화

03. 다이나믹 (동적 계획법) 알고리즘 수행

나름 자세하게 설명해 보았다. 다이나믹을 처음 접했을 때

상당히 난해했던 기억이 난다. 혹시나 나와 같은 사람이 있을까

최대한 설명을 해보지만.. 더 헷갈릴 수도 있겠다는 생각이 든다.

04. 메인 함수

멤버 함수를 하나하나 부르기 보다 편의 함수를

정의해서 함수 호출을 했다. 알고리즘 공부를 하면서

C++도 공부할 수 있으면 괜찮겠다 생각해서

클래스로 만들고 편의 함수도 만들어 보았다.