[단상]Dynamic Programming 에 대하여

어제 저녁 DP(Dynamic Programming) 에 관련된 흥미로운 주제로 세미나를 하고 오늘 아침 강아지 산책하면서.. 조금 더 큰 그림이 이해되었다.

어제 같은 주제에 대해서 나와 나누어 발표를 했던 J가 설명한 부분과 내가 설명한 내용이 완전히 다른 방법이 아니라..DP 문제를 해결하기 위한 Top-down 과 bottom-up 방식의 차이 같다라는 사실이다. 사실 Dynamic Programming 에 관하여 여전히 많은 사람들이 많은 문제들을 중심으로 다양한 연구가 진행되고 있는 것으로 이해하고 있다.

간단한 동전 교환에서 계단 오르는 문제에서 피보나치 순열을 중심으로 시작을 하게 된다. 하지만 실제 알고리듬 문제나 대회에서 나오는 수많은 다양한 문제들을 볼 때마다 상급자와 초급자의 실력의 차이는 매우 극명하게 나뉜다.

개인적으로 얼마전 까지는 DP 문제들이 문제를 초기화를 기준으로 수학적 귀납법인 방법이 주요한 아이디어가 아니었나 생각했었다. 그런데 어제 J 님의 노트와 설명을 들으면서.. 수많은 DP 문제들은 결국 전체 가능한 경우의 갯수를 헤아리는 문제가 대부분이라는 것을 깨달았다.

  (어제 설명을 들으면서... )  떠 오른 생각이란...

f(n) = f(n-1) + f(n-2) + f(n-3) 과 같이 경우의 수를 더하는 경우와...

f(n) = f(k) * f(n-k) 와 같이 경우의 수를 곱하는 경우가...

결국... 독립 사건과 종속 사건의 개념일 것라는 것이 스쳐갔다.

 

사실 고등학교 때 수학 선생님들만이 아니라.. 학부에서 확률 / 통계를 가르치던 교수들까지도...이 부분을 설명을 할 때.. 무언가 100% 명확하지 못하다는 것을 매번 느꼈고... 나 역시도 100% 이해를 하지 못한다는 답답함이 있었는데...결국 DP 문제에 와서도 부딪히는 것이 아닌가 하는 의심이었다.

 

아마도 내 생각이 맞다면...(틀릴 수도 있지만...) 이런 간단한 원인을 상급자들은 정확하게 파악해서..  대부분의 DP 문제들을 파악하고 해결책을 빠른 시간 내에 찾는 것이라는 심증(?)이 들었다.

Tokofe-LC1737-LC552.pdf

1.83MB