#169동아리 스터디 - 실행 횟수 세기

어느 알고리즘 동아리에서 동적 프로그래밍 스터디를 진행한다. 스터디 진행자는 참가자들이 강의 내용을 잘 이해했는지 확인하기 위해 다음 문제를 낸다.

이번 시간에는 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 때, 코드1과 코드2가 각각 몇 번 실행되는지 출력하시오.

피보나치 수 재귀호출 의사 코드는 다음과 같다.

fib(n) {if (n = 1 or n = 2)
then return 1; # 코드1
else return (fib(n - 1) + fib(n - 2));}

피보나치 수 동적 프로그래밍 의사 코드는 다음과 같다.

fibonacci(n) {f[1] <- f[2] <- 1;
for i <- 3 to n
f[i] <- f[i - 1] + f[i - 2]; # 코드2
return f[n];}

첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다.

코드1과 코드2가 각각 실행된 횟수를 한 줄에 공백으로 구분하여 출력한다.