[단계별로 풀어보기][재귀] 피보나치 수
피보나치 수 5 성공
| 1 초 | 256 MB | 83319 | 51139 | 43721 | 61.924% |
문제
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 n번째 피보나치 수를 출력한다.
예제 입력 1 복사
10
예제 출력 1 복사
55
n번째 피보나치 수를 출력하는 문제다.
소스코드는 아래와 같다.
간결하면서도 복잡해 보이는 코드다.
내가 문제를 푼 단계를 설명하겠다.
1)
피보나치 수를 구하는 함수 f(x)가 있다고 했을 때
f(x)=f(x-1)+f(x-2)이다.
2)
f(1)은 0이고 f(2)는 1이다.
재귀를 계속 따라가다 보면 모든 함수는 f(1)과 f(2)의 합으로 귀결된다.
따라서 n이 1일 때와 n이 2일 때만 정수를 리턴해준다.
3)
나머지일 때는 f(0)과 f(1)을 호출할 함수를 리턴해준다.
풀고 나서도 헷갈린다.
이 문제를 어떻게 이해해야 다음에 이런 종류의 문제를 만났을 때 헷갈리지 않고 잘 풀 수 있을지 모르겠다.
그래서인지 도전욕이 생겼다.
당연한 소리처럼 들릴지 모르지만 많이 푸는 것이 이런 종류의 문제를 잘 풀기 위한 정답일 것이다.
따라서 한동안은 재귀 문제를 많이 파야겠다.