📝 문제 설명
>
[문제]
피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/10870
🎨 풀이
💡 전체 코드
def fibo(num):
if num == 0 :
return 0
elif num == 1 :
return 1
else :
return fibo(num-1) + fibo(num-2)
n = int(input())
print(fibo(n))
> 핵심 : 재귀 함수 사용!
fibo(1) or fibo(0) 전까지는 계속 호출만 하다가 num이 1 또는 0이 되었을 때부터는 쭉 계산해서 쭉쭉 위로 올라가는 느낌으로 이해하면 된다.
🍦 코드 설명 (실행 순서대로 나열)
# main
n = int(input())
print(fibo(n))
1. n을 입력받는다.
2. fibo 함수를 실행한다. (출력은 실행 순서상 맨 마지막!! 아직 출력은 안한다!)
# fibo
def fibo(num):
if num == 0 :
return 0
elif num == 1 :
return 1
else :
return fibo(num-1) + fibo(num-2)
3. num이 0이라면 0을 return한다.
4. num이 1이라면 1을 return한다.
5. num이 2보다 같거나 큰 수라면 fibo(num-1) + fibo(num-2)를 return한다.
- 이 때, 함수 내부에서 그 함수를 두번이나 더 불렀기 때문에 재귀 호출이 계속된다.
그러다가 num이 0이 되거나, 1이 되는 순간 return해서 쭉 계산해서 점점 위로 올라오는 그런 절차를 따른다.
# main
print(factorial(n))
5. fibo(n) 함수에서 리턴된 값을 출력한다.
끝~
⭐ 느낀점
> 오늘은 그래도 잘 활용했다. 아직까지는 브론즈가 붙어있는 문제라 그런지 쉬운 것 같기도 하고! 그리고 또 며칠 전에 피보나치를 다른 방법으로 풀어봤기 때문에 조금 더 수월했던 것 같다. 잘했다!
'알고리즘 공부 > 백준' 카테고리의 다른 글
[백준] 2864번 - 5와 6의 차이 (파이썬) (0) | 2022.07.29 |
---|---|
[백준] 17478번 - 재귀함수가 뭔가요? (파이썬) (0) | 2022.07.28 |
[백준] 10872번 - 팩토리얼 (파이썬) (0) | 2022.07.26 |
[백준] 1026번 - 보물 (파이썬) (0) | 2022.07.25 |
[백준] 11047번 - 동전 0 (파이썬) (0) | 2022.07.24 |