dynamic programming

[Algorithm] DP(Dynamic Programming) / 동적 프로그래밍이란?

DP(Dynamic Programming) 이란? 동적 프로그래밍이라고도 불리는 동적 계획법은 분할 정복 기법과 굉장히 유사하다. 분할 정복 기법이란, 알고리즘을 짤 때 큰 문제를 한 번에 해결하지 않고 작은 여러 개의 문제로 나누어서 푸는 기법이다. 이렇게 풀다보면 같은 문제를 반복적으로 풀게되는데, 이를 매번 재계산하지 않고, 값을 저장해두었다가 재사용하는 기법이 바로 동적 계획법이다. 동적 계획법의 종류 Top-down - 하향식 계산법 - 큰문제부터 시작해 작은 문제로 분할 - 메모제이션 : 동일한 계산을 반복해야 할 경우, 한 번 계산한 결과를 메모리에 저장해두었다가 꺼내씀으롰 중복계산방지를 할 수 있게 하는 기법으로, 동적 계획법의 핵심 기술이다. 즉, 메모리라는 공간비용을 늘림으로써 계산에 ..