동적계획법(Dynamic Programing, DP)
동적계획법 동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 동적 계획법(Dynamic Programming)은 이름만으로 무엇을 의미하는지 알 수 없기 때문에 오해가 많이 생기는데, 동적 계획법(Dynamic Programming)이라는 말을 처음 사용한 벨만은, Dynamic 이라는 단어가 멋있어서 선택했다고 한다. 1. 큰 문제를 작은 문제로 동적 계획법은 큰문제를 작은문제를 나눠서 푸는 기법이다. 그래서 동적 계획법의 핵심이 "큰문제를 작은문제를 나눠서 푼다." 이다. 이 방식은 분할 정복과 같은데 다만 분할 정복은 동적계획법과 달리 계산한 부분문제를 한번만 쓰고 더 이상 쓰지 않기 때문에 메모이제이션이 필요하지 않다. 분할 정복과 동적계..
코딩/알고리즘
2017. 8. 27. 18:34