[알고리즘] 다이나믹 프로그래밍 (DP)

다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누고

그 작은 부분 문제들이 반복되는 것을 이용하여 풀어가는 방법이다.

모든 작은 문제들을 단 한번만 풀어야 하며, 그 결과를 어딘가 기록해 둠으로써 재사용한다.

 

부분 문제를 푸는 순서에 따라서 Top-Down과 Bottom-up으로 나뉜다.

 

메모이제이션은 자꾸만 반복되지만 그 결과값은 변하지 않는 작은 ㅁ누제들의 결과값을 저장하는 것을 의미한다.

메모이제이션을 통해 이미 결과값이 기록되는 특정 문제가 반복될 때, 불필요한 계산은 패스하고 기록되어 있는 값만 불러오면 아주 빠르게 해결할 수 있다.