다이나믹 프로그래밍 기법이란 메모리 공간을 약간 더 사용함으로써 연산 속도를 비약적으로 증가시킬 수 있는 방법을 의미합니다.
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있습니다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이며, 다음과 같은 형태로 끝없이 이어집니다.
이러한 피보나치 수열은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현할 수 있습니다.
프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있습니다. 수열 자체가 여러 개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문입니다.
다시 피보나치로 돌아와서, 위의 수식을 해석하면 다음과 같습니다.
그렇다면 이 점화식에 따라 실제로 피보나치 수를 구하는 과정을 어떻게 표현할 수 있을까요? n번째 피보나치 수를 f(n)이라고 표현할 때 4번째 피보나치 수 f(4)를 구하려면 다음과 같이 함수 f를 반복해서 호출할 것입니다. 그런데 f(2)와 f(1)은 항상 1이기 때문에 f(1)이나 f(2)를 만났을 때는 호출을 정지합니다.
재귀호출을 이용한 기본적인 피보나치 함수
func fibo(_ x: Int) -> Int {
if x == 1 || x == 2 {
return 1
}
return fibo(x - 1) + fibo(x - 2)
}
print(fibo(4))
그러나 이러한 방식으로 피보나치 코드를 작성하게 되면, n의 개수가 커지면 커질수록 수행 시간이 기하급수적으로 늘어나므로 심각한 문제를 초래할 수 있습니다. 이러한 소스코드의 시간 복잡도는 O(n2) 가 소요됩니다. 만약 n이 30이 되면, 약 10억 가량의 연산을 수행해야 합니다.
다음은 f(6) 때의 호출 과정입니다.
