알고리즘 - 동적 프로그래밍 : Dynamic Programming

Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말 분할정복과 유사함 분할 정복과 동적 프로그래밍의 차이는 작은 문제가 중복이 일어나는지의 차이이다. 분할 정복은 큰 문제를 작게 나누어 푸는 방법이며, 동적 프로그래밍은 작은 문제들이 반복되는 것이다. 동적 프로그래밍의 답은 일정하면 바뀌지 않는다. 동적 프로그래밍 방법과 조건 모든 작은 문제들을 한번만 풀어야 한다. 정답을 구한 작은 문제들을 어딘가에 메모하고 큰 문제를 풀 때 작은 문제가 나타나면 앞에서 메모한 결과를 이용해서 큰 문제를 푼다. 동적 프로그래밍의 사용 조건은 아래와 같다. 작은 문제가 반복이 일어나는 경우 문제가 구할 때마다 정답이 같은 경우 Memoization 메모제이션은 동적 프로그래밍에서 작..