topcoder PBG에서 시작된 Dynamic Programming의 여정...

topcoder PBG문제를 선택한게... 아직 끝나지 않은 Dynamic Programming의 여정의 시작이였습니다.

PBG문제를 조금 소개하면, PB와 PG, 2개의 그룹으로 나눠서, 각각 Dynmic Programming을 구현하고, 둘의 결과를 합쳐서 푸는 문제였습니다. PBG는 비교적 최근 치뤄진 SRM768의 난이도 500문제로... 뒷얘기도 기니까, 생략하고... 결론은 답을 봐도 별로 이해가 가지를 않아서... - -;;;

PBG문제의 해설에 이렇게 적혀 있는대요.요약하면,
PBG문제의 풀이가 이해가지 않으면, https://atcoder.jp/contests/dp/tasks/dp_j 여기가서 문제좀 풀어 보고 오라고... - -;;;

https://atcoder.jp/contests/dp/tasks/dp_j <- 이것도 상당히 빡쌔 더라구요.
그래서, Dynamic Programming에 대해서 좀 검색하다가,

이거를 찾아서, 여기서 좀 풀어도 보고, 해메다가...
https://practice.geeksforgeeks.org/problems/-minimum-number-of-coins/0
답이라고 누가 풀어놓은게 잘 못 풀어 놓은 것임을 깨닫고, 분노를 삭히며,
이제 좀 Dynamic Programming을 공부좀 해야겠다. 하는 와중에...

같이 스터디 하는 친구가 https://www.youtube.com/watch?v=krZI60lKPek&feature=share 이 링크를 줍니다.
MIT 6.046J Design and Analysis of Algorithms 수업에서 Dynamic Programming에 대해서 설명한 MIT OpenCourseWare 입니다.

영상은 50분이 넘는 영상이지만, 대략 7~8분 사이에 Dynamic Programming의 많은 내용을 훅훅 지나 가더군요.
MIT친구들이야 똑똑하니까, 저정도만 설명해도, 다 알아 듣나 봅니다. (좌절 +1)
몇년전 스터디에서, Dynamic Programming을 좀 보기는 했었는대, 유튜브로 다시 보니까,
당췌 뭔소리인지 모르겠는대, 저렇게 후딱 그냥 지나가는지... (좌절 +2)

찾다 찾다 좀 쉽게 설명한 영상을 찾아서, 바로 이것 -> https://www.youtube.com/watch?v=PafJOaMzstY
이제 좀 개념을 잡아 가는 것 같네요. (희망+1)

다시 MIT유튜브 강의로 돌아와서, 요기 -> https://www.youtube.com/watch?v=krZI60lKPek&feature=share

영상의 시작에서는 (1,1)→(M,N)까지 가는 길이 경우의수를 DP로 설명하고 있습니다.
이문제에 대한 자세한 내용은 → (1,1)→(M,N)까지 가는 길의 경우의 수

5분 부터 7분 정도 까지의 내용이 '어떤 잔돈이 있을 때, 잔돈을 줄 수 있는 최소 동전의 수' 문제를 설명하고 있습니다.
이문제에 대한 자세한 내용은 → Minimum Coin Change Problem

위의 문제를 코딩한 김에, 'Coin change problem'으로 알려저 있는,
'잔돈을 만들 수 있는 동전 조합의 수'문제도 코딩해 보았습니다.
이문제에 대한 자세한 내용은 → Coin change problem