[알고리즘] Dynamic Programming (동적 프로그래밍, 동적 계획법, DP)

개념 프로그래밍은 컴퓨터 프로그래밍을 의미하는 것이 아닌 테이블을 만든다는 의미. 이미 했던 연산이 반복되는 결점을 보완하기 위해 동적계획법(Dynamic Programming, DP)이 고안되었다.

원리는 처음 진행되는 연산을 기록해 두고, 이미 진행했던 연산이라면 다시 연산하기보다 기록되어 있는 값을 가져오는 기법을 사용함. (이러한 메모이제이션이 동적 프로그래밍 중 하나) 알고리즘을 짤 때 분할정복 기법을 사용하는 경우가 많다.

큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는기법인데, 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생김. 그 문제들을 매번 재계산하지 않고 값을 저장해두었..........