programming
프로그래머스 피보나치 수 파이썬 풀이 및 해설
by Kitle · 2020. 08. 14.
이번 포스팅에서는 프로그래머스의 피보나치 수 퀴즈를 파이썬으로 풀어 보겠습니다.
문제 출처 프로그래머스 : 프로그래머스에서 보기
풀이 깃허브에서 보기 : 깃허브로 이동
문제 설명
문제는 다들 아시는 피보나치 수 풀이 입니다. 프로그래밍 배우실때 한번쯤은 다 풀어봤을 유명한 수학 문제중에 하나죠.
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수라고 할 수 있죠. 다들 무엇으로 배웠나요? 다들 재귀함수를 공부하면서 재귀함수로 풀었을 것으로 예상됩니다. 그럼 우선 재귀함수로 풀어보겠습니다.
논리적으론 맞지만 문제의 의도에 부합하지 않는 풀이
def fibo(n):
if n < 3:
return 1
else:
return fibo(n-1) + fibo(n-2)
print(fibo(1000))
일단 간단하게 재귀함수를 돌려본다면, 바로 에러를 뱉을 것입니다.
RecursionError: maximum recursion depth exceeded in comparison
파이썬에서 재귀함수의 depth를 벗어나는 것이죠. 퀴즈에서는 조건이 최대가 100000 이므로 위와 같은 방법으로 풀 수 없습니다.
정상풀이
피보나치를 풀 수 있는 알고리즘은 정말 여러가지가 있는데요. 이번에는 python list 를 활용하여 풀어보도록 하겠습니다.
def solution(n):
fibo = []
for num in range(0, n+1):
if num == 0:
fibo.append(0)
elif num == 1:
fibo.append(1)
else:
fibo.append(fibo[num - 2] + fibo[num - 1])
return fibo[n] % 1234567
솔루션 및 해설
list 자료구조를 활용하여 피보나치의 n 결과를 앞에서부터 리스트에 채운다. 0, 1, 1, 2, .... 이런식으로 맨뒤에 append 합니다.
n까지의 값을 바로 앞의 값을 활용하여 계산하므로 재귀함수보다는 훨씬 빠릅니다.
그리고 마지막 결과 값에 %1234567을 한것은 퀴즈에서 나눈 나머지를 물어보았기 때문인데요. 아마 저 조건이 추가 된것이 재귀함수를 쓰지말라는 뜻일지, 아니면 결과값이 너무 길어져 결과 출력에 이슈가 있어서 그럴까봐 그런것 같기도 하네요.
사실 퀴즈는 n의 입력 최소값이 2 이상이기 때문에 입력값 n이 0,1은 크게 신경쓰지 않아도 됩니다. 하지만 수학적으로 볼때 맞지 않을 수 있으므로 깔끔하게 n = 0 이면 0을 출력을, n = 1이면 1을 출력하는 부분도 깔끔하게 처리해주면 좋을것 같네요.
물론 이 풀이보다 더 좋은 알고리즘과 수학적인 방법으로 풀 수도 있습니다. 이 방법은 단순히 해당 퀴즈에 Pass 되는 수준이므로 참고하시기 바랍니다.
