[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다. 피보나치 수열과 같이 한 번 푼것을 여러번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법으로 사용한다. 그리고 다이나믹 프로그래밍은 두가지 가정하에 사용할 수있는데 1) 큰 문제는 작은 문제로 나눌 수 있다. 2) 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. 즉, 다이나믹 프로그래밍은 큰 문제를 해결하기 위해서 그것을 작게 나누어 해결한 뒤 그것을 이용하여 답을 구하는 것이다. 하지만 이 과정이 분할정복과 다른 점은 메모제이션(Memozation)이 사용된다는 점이다. 이미 계산한 것을 저장하는 것으로 나중에 동일한 계산을 할 때는 저장된 값을 반환하여 사용하..
