[알고리즘] 15. 다이나믹 프로그래밍(Dynamic Programming)

1. 다이나믹 프로그래밍(Dynamic Programming, DP)
: 하나의 문제는 단 한 번만 풀도록 하는 알고리즘.
한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법.


* 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다.

 

예시) 피보나치 수열의 점화식

D[i] = D[i-1] + D[i-2]
1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구해야 함
→ 이미 해결한 문제를 다시 반복적으로 해결하여 비효율적


2. DP 사용 조건
1번 가정 : 큰 문제를 작은 문제로 나눌 수 있다.
2번 가정 : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 

→ 어려운 문제가 있으면 그것을 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것.
이 과정에서 메모이제이션(Memoization)이 사용된다는 점이 분할정복과 다르다.
이미 계산한 결과는 배열에 저장하여 나중에 동일한 계산을 해야할 때는 저장된 값을 단순히 반환하기만 하면 되는 것.