동적계획법의 기초

동적 계획법이 왜 쓰이는지에 대해 궁금한 사람들을 위해 작성합니다.

동적 계획법이란, 이미 계산돼있는 값을 추후에 다시 계산하지 않고 가져다쓰기 위함입니다.

답을 재활용한다고 생각하시면 편합니다.

 

동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. 

 

팩토리얼을 이용한 동적 계획법은, 둘다 시간 복잡도가 log(N) 이기 때문에 적합하지 않습니다.

조금 더 자세한 예를 위해 피보나치 수열 문제를 가져왔습니다.

 

https://www.acmicpc.net/problem/2747 백준 2747번 피보나치 수

 

 

 

위와 같은 방식은 설명을 위한 재귀지, 일반적으로 사용하는 방식은 아닙니다.

 

 

시간 단위는 millisecond 입니다.

 

왜 이렇게 시간 차이가 많이 나냐고 할 수 있는데, 생각해보면 쉽습니다.

 

예를들어 재귀를 이용한 방법은

Fibonacci(n-1) + Fibonacci(n-2) 의 재귀를 사용합니다.

이는 재귀를 계속 파고 들어간다는건데, Fibonacci(47) 을 구하게 되면

이런식으로 재귀를 계속 파고 들게 됩니다. 

보면 왼쪽 Fibonacci(46)에서 Fibonacci(45) 의 값을 이미 계산해놨는데, 오른쪽 Fibonacci(45) 의 값을 또 계산하게됩니다.

 

중복되는 연산을 피하기 위해 왼쪽 FIbonacci(46)에서 Fibonacci(45)의 값을 계산했을 때 미리 저장해놓고

오른쪽의 Fibonacci(45)를 만났을 때, 저장해 놓은 값만 그대로 사용하면 되는 겁니다.

 

이처럼 메모리를 사용하여 시간을 줄이는 방법을 동적 계획법이라고 합니다.

 

https://www.acmicpc.net/problem/2747 <- 이 문제 꼭 풀어보세요.