재귀호출(recursive), 동적 계획법(Dynamic Programming)

알고리즘의 기본이라고 할 수 있는 재귀호출과 동적 계획법에 대해서 알아보자!

 

 

 

 

재귀호출

- 문제를 해결 하기 위해, 기존 문제를 작은 문제로 나눠서 문제를 푸는 것

- Big -> Small

 

 

 

동적 계획법

- 문제를 해결 하기 위해서, 작은 문제의 해결법을 이용해 기존 문제를 해결하는 것

- Small -> Big

 

 

 

그렇다면, 여기서 모든 재귀호출을 동적 계획법으로 표현할 수 있을까?

 

 

 

정답은 아니다. 동적 계획법이라면, 특정 단계의 문제를 해결하기 위해서, 특정 이전 단계의 문제들을 모두 해결해야 한다는 것이다.

 

 

 

하지만, 특정 이전 단계들의 문제들을 차례로 해결하지 않으면, 특정 단계의 문제를 해결할 수 없게 된다.

 

 

 

따라서, 모든 재귀호출이 동적계획법으로 표현될 수 있는 것이 아니다.

 

 

 

동적 계획법으로 특정 단계의 해결법을 구하려면, 특정 단계 이전 문제들이 모두 해결되어야 한다.