25% 25%

동적 계획법(Dynamic Programming)의 정의 어떤 문제가 반복적이고 최적 하위구조로 이루어질 때, 하위구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법 최하위 구조(Optimal Substructur)란 전체 문제의 답이 부분 문제의 답으로부터 만들어지는 구조를 말한다. 예를 들어 어떤 문제를 7개의 하위문제로 나눌 수 있을 때, 7개의 하위문제의 답을 모두 얻어야 이 문제의 답을 구할 수 있다면 이 문제는 최적 하위구조를 갖추었다고 할 수 있다. 분할정복과 비슷해 보이지만, 분할정복은 문제를 큰부분에서 작은부분으로 나누는데 반해(Top-Down), 동적 계획법은 제일 작은 부분부터 큰 문제로 풀어 올라간다(Bottom-Up). 또한 분할 정복은 나눈 문제들을 완전히 새로..