10.1 피보나치 수열

피보나치 수열은 재귀적인 방법으로 해결하는 대표적인 알고리즘입니다. 하지만 피보나치 수열에서는 내부적으로 두 번의 재귀를 수행하여 재귀 호출 횟수는 2의 n승으로 수행 비용이 많이 들어갑니다.

만약 한 번 구한 항의 값을 기억해 두었다가 다시 호출할 때 이를 이용하면 비용은 줄어들어요. 이와 같이 경험한 정보를 이용하여 문제를 해결하는 것을 동적 프로그래밍 기법이라 말합니다. 여기에서는 피보나치 수열을 재귀적인 방법과 동적 프로그래밍 방법으로 해결하는 것을 비교해 볼게요.

다음은 피보나치 수열을 재귀적인 방법으로 구현한 코드입니다.

다음은 동적 프로그래밍으로 구현한 코드입니다. 수행한 경험이 있는 값들을 보관하는 테이블이 필요합니다. 테이블의 0항은 0으로 1과 2항은 1로 설정하고 나머지는 0으로 초기화합니다. 테이블에 값이 0이면 계산하고 0이 아니면 테이블의 값을 반환합니다.

다음은 둘의 수행 시간을 비교하기 위한 테스트 코드예요.

▷ 실행 결과

수행 결과를 보면 재귀 호출을 이용하여 구현한 피보나치 수열은 n이 커질 수록 소요하는 시간은 기하급수적으로 늘어나는 것을 볼 수 있습니다. 하지만 동적 프로그래밍은 경험 정보를 이용하기 때문에 매우 빠르게 수행함을 알 수 있습니다.