알고리즘 연습 [피보나치]
피보나치
문제
피보나치 수는 F(0) = 0, F(1) = 1일 때, 2 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 점화식입니다. 2 이상의 n이 입력되었을 때, fibonacci 함수를 제작하여 n번째 피보나치 수를 반환해 주세요. 예를 들어 n = 3이라면 2를 반환해주면 됩니다
나의 풀이
def fibonacci(n):
return n if n == 0 or n ==1 else fibonacci(n-1) + fibonacci(n-2)
실행시간이 5초 이상이어서 실행이 중단됨..-> 재귀함수를 사용하지 않고 플어야 하는듯.
리스트에 사용해서 풀면 정답이 뜨는데
def fibonacci(n):
ans = [0, 1]
for i in range(2, n+1):
ans.append(ans[i - 1] + ans[i - 2])
return ans[i]
다른 풀이
def fibonacci(num):
a, b = 0, 1
for i in range(num):
a, b = b, a+b
return a
핵심은 -> 재귀함수로 풀면 안되고 for문으로 input값까지 돌려야 한다는 것 같다.
재귀함수를 쓰면 중복되는 피보나치 함수를 계속 계산해야함 -> 피보나치는 반복 알고리즘이 재귀보다 성능이 좋음을 알려주는 예