[Python] 파이썬 예제. 피보나치 수 풀이

본 게시글은 http://tryhelloworld.co.kr/ 에서 출제된 문제를 가지고 풀이한 글입니다.

문제

피보나치 수는 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(num):
    answer = 0
 
    return answer
 
# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(fibonacci(3))

풀이

def fibonacci(num):
    answer = [0,1]    #list의 초기값을 0,1로 지정
 
    for i in range(2,num+1):#i는 list의 주소를 뜻함
        answer.append(answer[i-1]+answer[i-2])#list에 추가하겠음
    #print(answer)  #이것은 피보나치 list를 출력해 보기 위해
    #print(i)       #이것은 리스트 주소가 잘 돌고있는지 확인하기위해
    return answer[-1]    #리스트에서 가장 마지막것만 출력해준다!
 
# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(fibonacci(5))

처음에 피보나치가 무엇인지도 몰라서 되게 힘들었던 문제입니다.

피보나치는 이렇습니다

1 + 1 + 2 + 3 + 5 + 8 + 13......

answer[1] answer[2]   answer[3]     answer[4]     answer[5]    answer[6]     answer[7] 

여기서 규칙을 찾아보겠습니다.

1. answer은 1씩 올라가고 숫자들을 저장해야 하니 list로 만들 수 있겠다.

2. answer[3] = answer[2] + answer[1],    answer[4] = answer[3] + answer[2] ............

2-1. 이것은 즉. answer[i] = answer[i-1] + answer[i-2] 로 생각할 수 있겠죠?

코드풀이입니다.

바로 위에서 피보나치의 규칙을 보셨듯이 현재 필요한것은

list가 필요해서 2번째줄에 선언을 해주었고 그것의 초기값을 0,1로 했습니다.

그리고 리스트를 올려줘야 하기 때문에 for반복문을 사용했구요 (초기값은 2이고 입력값의 +1만큼만 진행합니다.)

- num+1의 이유는 list에 0의 값이 포함되어 있기 때문에 자리를 차지해서 +1만큼 계산을 더해야합니다.

- num+1 일때:[0, 1, 1, 2, 3, 5]

  num     일때:[0, 1, 1, 2, 3]

(위 값은 5를 집어넣을때 입니다)

append는 list 삽입을 뜻합니다.

(answer[i-1]+answer[i-2])은 위에 보신 규칙을 보시면 이해하기 빠르실 것입니다.

return에 [-1]을 넣는이유?

[-1]을 넣지 않는다면 list가 그대로 출력되서 

이렇게 출력이 될것입니다.

그러므로 마지막 list의 값인 5를 출력하기 위해서 [-1]번째를 return한다고 생각하시면 됩니다.