[이론] 다이나믹 프로그래밍 (Dynamic Programming, DP)

한 번쯤은 꼭 짚고 넘어가야 할 개념이라고 판단되어 정리한다.

 

다이나믹 프로그래밍이란, 동일한 문제는 한 번만 풀도록 하는 것을 말한다. (시간 효율성을 위해서 전에 계산해뒀던 결과값을 저장할 수 있는 공간을 마련한다.) 대표적인 예시는 피보나치 수열이 있다. 

 

다이나믹 프로그래밍은 다음 두 조건을 만족할 때 사용할 수 있다.

1) 큰 문제를 작은 문제로 나눌 수 있다. (작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.)

2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (동일한 작은 문제를 반복적으로 해결해야 한다.)