안녕하세요.우리는 지난 포스팅들을 통해서 동적 프로그래밍(Dynamic programming)의 3가지 예시에 대해 살펴보았습니다.이번 포스팅에서는 예시들과 같은 최적화 문제에 동적 프로그래밍을 적용하기 위해 가져야 하는 두 가지 중요한 구성요소,최적 부분 구조와 중복되는 부분 문제에 대해 살펴보도록 하겠습니다.어떤 문제에 대해서 동적 프로그래밍을 적용하기 위해서 해당 문제가 가져야 할 두 가지 구성요소는,최적 부분구조와 중복되는 부분 문제입니다. 하나씩 자세히 살펴보도록 하겠습니다. 1. 최적 부분 구조(Optimal substructure) 동적 프로그래밍을 적용하기 위해 가장 먼저 확인해야 할 것은 최적해의 구조의 특징입니다.기본 문제의 최적해가 부분 문제의 최적해를 포함하고 있을 때, 우리는 그 ..
