동적 프로그래밍

최근 편집: 2022년 12월 16일 (금) 04:06

동적 프로그래밍(Dynamic programming)이란 어떠한 문제를 해결하기 위해서 그 문제의 부분 문제를 해결함으로서 효율적으로 문제를 해결하는 방법이다. 이는 1957년에 R. Bellman에 의해서 제안되었다.[1]

동적 프로그래밍은 주로 다양한 수학적 최적화 문제를 해결하기 위해서 사용되며, 경제학, 제어이론등의 다양한 분야에 응용되고 있다.

최적 조건

임의의 동적 프로그래밍식이 최적화 문제에 대하여 최적임을 판정할 수 있는 조건은 벨만의 최적 원리이다. 또한, 이에 대한 필요 조건으로는 벨만 식이 있다.

예시

피보나치 수열

피보나치 수열(Fibonacci sequence)은 점화식 으로 정의되는 수열이다.

재귀적인 방법으로 계산을 시도하면, 의 시간복잡도를 얻어서 매우 비효율적이라고 할 수 있다. 이를 개선시키기 위해서 동적 프로그래밍을 통해서 계산을 시도하면 의 시간복잡도를 얻고 효율적으로 계산할 수 있다.[주 1]

최대 공통 부분 문자열

최대 공통 부분 문자열(Longest common substring) 문제는 임의의 문자열 , 가 주어졌을 때, 최대의 길이의 공통된 부분 문자열을 찾는 문제이다.

두 문자열의 모든 부분 문자열을 돌아본다면, 의 시간복잡도를 얻지만, 동적 프로그래밍을 통해서 더 효율적으로 계산할 수 있다.

다음과 같은 식은 시간에 계산될 수 있으며, 이는 효율적이다.

부연 설명

  1. 하지만 더 효율적인 방법으로, 행렬 곱을 이용하여 시간에 수행될 수 있다.

출처

  1. Richard E. Bellman. 《Dynamic Programming》. Princeton University Press. ISBN 9780691146683.