[Python & Algorithm] Dynamic Programming(동적프로그래밍)

✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나는지 아닌지' 에 차이가 있다. 분할정복은 큰 문제를 해결하기 어려워서 단지 작은 문제로 나누어서 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 하지만 동적프로그래밍은 작은 부분문제들이 반복되는 것을 이용해 문제를 풀어낸다. 2) 다이나믹 프로그래밍의 방법 모든 작은 문제들은 한번만 풀어낸다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해둔다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 3) 다이나믹..