동적알고리즘(동적계획법) 예제와 설명

동적계획(動的計劃, dynamic programming)은 어떤 알고리즘이 부분 문제 반복과 최적 기본 구조라는 특징을 가지고 있을 때, 이 알고리즘의 실행시간을 줄이는 방법이다. 수학자인 리처드 벨만이 1953년에 '동적계획'이라는 용어를 만들었다.

목차 [숨기기] 1 예제 1.1 피보나치 수열 2 동적계획을 이용한 알고리즘 3 바깥고리 4 참고문헌

예제 [편집]

피보나치 수열 [편집]

보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.

function fib(n)
 if n = 0 or n = 1
  return 1
 else
  return fib(n-1) + fib(n-2)

이때, fib(5)를 구한다고 한다면 계산은 다음과 같이 이루어진다.

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

여기에서 세 번째 줄의 fib(2)가 중복되어 계산되고, 이것은 전체적인 계산 속도를 떨어뜨린다. 이 알고리즘의 시간 복잡도는 지수 함수가 된다.

여기에서 각 함수의 계산값을 저장하는 객체 m을 추가하면, 이 알고리즘은 다음과 같이 바뀐다.

var m := map(0 → 1, 1 → 1)

function fib(n)
 if n not in keys(m)
  m[n] := fib(n-1) + fib(n-2)
 return m[n]

이렇게 각 계산값을 저장하면, 중복 계산이 줄어들고 시간 복잡도는 O(n)이 된다.

동적계획을 이용한 알고리즘

최장 공통 부분 수열 - 주어진 두 개 이상의 수열의 부분수열이 되는 가장 긴 수열을 찾는 알고리즘

• Cocke-Younger-Kasami (CYK) 알고리즘 - 주어진 문맥무관문법으로 원하는 문자열을 만들 수 있는지 판정하는 알고리즘
• 비터비 알고리즘
• Earley algorithm
• 벨만-포드 알고리즘
• 데이크스트라 알고리즘 - 주어진 시작점과 종료점 사이의 가장 짧은 경로를 찾아내는 알고리즘
• 플로이드-와샬 알고리즘
• chain matrix multiplication의 최적 곱셈 순서
• 부분집합 합 알고리즘
• 배낭 문제

- 출처 : 위키백과

동적계획법의 소개

KOI에 관심을 갖고 계신 분이라면 동적계획법(Dynamic programming : 다이나믹 프로그래밍)에 대해서 조금은 들어 보셨으리라 생각합니다. 동적계획법을 사용하면 여러 최적해 문제를 쉽고 깔끔해서 풀 수 있기 때문에 필히 익혀 두어야 합니다.

참고로 KOI에서는 13회부터 매년 세 문제 중 한 문제는 동적계획법 문제를 출제하고 있습니다. 이제 동적 계획법이 차지하는 비중이 얼마나 막강한지 아시겠죠?

동적계획법의 정의 - 작은 문제들의 해를 배열에 저장한 다음 그것들을 순환적(recursive)인 성질을 이용하여 결합해 큰 문제의 해를 구한다.

특징을 차근차근 살펴보기로 하겠습니다.

1. 동적계획법은 해를 저장하는 배열을 사용한다. (흔히 테이블이라고 하죠)

동적계획법이 분할정복 (Divide and conquer : 큰 문제의 해를 쪼개 작은 문제의 해를 구하는 방식)과 구별되는 가장 큰 특징입니다. 배열을 이용하면 똑같은 문제에 대한 답을 여러 번 구할 필요가 없다는 것입니다.

2. 동적계획법은 순환적인 성질을 이용한다.

동적계획법은 '점화식'이란 것을 사용합니다. 이 점화식은 큰 문제와 작은 문제간의 관계를 나타내는 식입니다. 큰 문제를 풀기 위해서는 작은 문제에 대한 답을 미리 구해 놓아야 한다는 뜻이 됩니다.

동적계획법이 확실히 유용한 알고리즘 설계기법이긴 하지만 어떤 문제에든지 적용할 수 있는 것은 아닙니다. 동적계획법이 성립하기 위해서는 최적화 원리 (Principal of optimality)가 성립해야 합니다.

최적화 원리 - 한 문제에 대한 해가 최적이면 그 문제를 이루는 부분 문제들의 해도 최적이다.

[출처] 동적계획법의 소개|작성자 seedkjb

예제 문제

1. 최대증가 수열(Up-Sequence)

2. 최대 공통 문자열(LCS)

3. 기업투자

4. 동전교환문제(조합)

5. k-napsack

[출처] 동적계획법(Dynamic Programming)|작성자 무냉스