1170년 이탈리에에서 태어난 수학자 페오나르도 피사노(Leonardo Pisano)는 그 유명한 피보나치(Fibonacci) 수열을 구하는 알고리즘을 발견했습니다(피보나치는 그의 별명입니다). 알고리즘에서는 피보나치를 빼놓을 수 없지요.
간단한 코드로 표현한다면 다음과 같습니다.
const fibonacci = function(num) {
// base case
if (num === 0) return 0;
if (num === 1) return 1;
// recursive case
return fibonacci(num-2) + fibonacci(num-1);
}하지만 이 알고리즘이 성능 면에서 최선일까 의심을 해봅니다.
왜냐하면 num의 값이 커질수록 재귀적 호출이 폭발적으로 늘어나기 때문입니다.
그래서 피보나치 알고리즘의 경우에는 재귀 알고리즘을 이용하는 것보다 직접 for나 while 루프를 돌리는 것이 더 빠르고 효율적입니다.
...
다음의 그림을 보면 위의 연산이 많은 중복을 발생시키는 것을 볼 수 있습니다.
알고리즘에 있어서 불필요한 중복은 치명적이지요.
그렇다고 재귀의 기법이 결코 틀린 것은 아닙니다. 알고리즘의 '간결함'이라는 측면에서 재귀 기법이 필요하고, 불필요한 중복을 피할 수만 있다면 재귀를 이용하는 것이 더 바람직할 것입니다.
이럴 때 사용되는 것이 동적 프로그래밍입니다.
동적 프로그래밍은 알고리즘의 효율성을 향상시키기 위해서 알고리즘의 수행 도중에 계산한 결과를 테이블에 저장해 두었다가 재활용하는 기법입니다.
위의 피보나치 수열 알고리즘을 예로 든다면, 중복된 함수의 결과를 지정된 테이블에 저장해 두었다가, 같은 함수가 호출될 시 그 값을 바로 반환해주는 것이 동적 프로그래밍 기법이 되겠습니다. 매우 효율적인 알고리즘이지요.
다음의 코드는 동적 프로그래밍 기법을 이용한 피보나치 수열 알고리즘입니다.
코드를 직접 보는 것이 이해하기가 쉬울 것입니다.
const fibonacci = function(num) {
// memoization : 중복을 피하기 위해 값을 저장할 테이블입니다.
let memo = new Array(num+1).fill(-1); // -1로 초기화 시켜줍니다.
memo[0] = 0;
memo[1] = 1;
let aux = function (num) {
// base case
if (num === 0 || num === 1) {
return num;
} else if (memo[num] > -1) {
return memo[num]; // memo 테이블에 이미 값이 존재하다면 재귀를 돌지 않고 그 값을 반환해줍니다.
}
// recursive case
return memo[num] = aux(num-2) + aux(num-1); // memo 테이블에 값이 존재하지 않다면, 즉 처음 호출되는 함수라면 memo 테이블에 값을 추가해줍니다.
}
return aux(num);
}위와 같이 memo 테이블에 함수의 결과를 저장해준다면, 같은 함수가 호출될 시에 불필요한 재귀를 돌지 않고, 그 값만을 반환받을 수 있습니다. 그렇다면 훨씬 더 효율적인 알고리즘이 되는 것이지요.
이러한 동적 프로그래밍 기법은 실전에서 구사하기는 쉽지 않다고 합니다. 하지만 동적 프로그래밍이 제공하고 있는 '아이디어'를 자기의 능력에 맞게 실전 프로그래밍에서 활용하는 것은 권장할 만합니다.
