Dynamic Programming (동적 프로그래밍)

Dynamic Programming (동적 프로그래밍)

Dynamic Program은 복잡한 문제를 간단한 하위 문제로 나누어서 푸는 방법입니다.

겹치는 여러가지 문제들을 조금 간단한 문제들로 나누어서 푸는 방법이라 원래의 해결책보다 더욱 적은 시간이 드는 방법입니다. 동적 프로그래밍의 배경은 간단한데요. 한 문제의 다른 부분들을 각자 해결하여서 그 합이 전체의 문제 해결을 이루는 방법입니다. 이러한 각자해결하는 작은 문제들은 주로 같은 문제의 반복들이 많이 있는데, 그러한 반복을 한번만 수행함으로써 계산의 횟수를 줄일 수가 있습니다. 한번 수행한 해결은 다음에 똑같은 문제가 나왔을 때에 저장이 되어서 간편히 불러들이기만 하면되죠.

예를 들어서 피보나치 수열을 찾는데에 다섯번째 수열을 찾는다면

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)는 세번 반복되므로 일단 처음 나왔을때 저장을 하여서 다시 나올때에 불러들이기만하면 컴퓨터의 연산을 줄일 수 있는 방법입니다.

 

이러한 Dynamic Programming은 물론 전반적인 프로그래밍 기법에서 많이 쓰이기도 하지만, 특히 Bioinformatics의 프로그래밍에 많이 나오는 개념이고 자료의 크기가 큰 경우에는 거의 대부분 쓰여지니 잘 알아두는게 좋겠네요.