동적계획법

[동적 계획법 - Dynamic Programing] DP란?

DP란? DP, Dynamic Programming(동적 계획법)은 무엇일까? DP란, 하나의 큰 문제를 작은 문제로 나누어 해결하는 기법을 의미한다. 특정한 알고리즘을 지칭하는 것이 아니라, 기법 그 자체를 의미한다. 같은 DP로 문제를 풀어도 다른 알고리즘을 이용할 수도 있다는 것이다. DP가 무엇인지 처음 듣는 사람은 문제를 작은 문제로 나누어 해결하는 기법이 왜 Dynamic Programming이라 불리는 것일까, 하고 궁금증을 가질 수도 있다. 이에 대한 대답은 그저 '멋있어서'이다. Dynamic Programming이란 명칭을 고안한 Richard Bellman에 따르면 말이다. DP는 왜 중요할까? 백준, 코드포스 등 PS(Problem Solving) 사이트에서 문제를 풀다 보면 DP로..