[Level1] 피보나치 수 (Fibonacci)

1. 문제 

피보나치 수는 F(0) = 0, F(1) = 1일 때, 2 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 점화식입니다.  2 이상의 n이 입력되었을 때, fibonacci 함수를 제작하여 n번째 피보나치 수를 반환해 주세요.  예를 들어 n = 3이라면 2를 반환해주면 됩니다.

2. 풀이

1) 내가 작성한 코드

① Recursion을 이용한 풀이

: 풀이는 맞지만 숫자가 커지게 되면 시간이 오래걸려 출력이 되지 않는 문제가 발생했다.

 
def fibonacci(num):
    if num < 2:
        return num
    else:
        return fibonacci(num-1)+fibonacci(num-2) 

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(fibonacci(7))

② for문을 이용한 풀이

def fibonacci(num):
    answer = 0; f0 = 0; f1 = 1

    if num<2:
        return num
    else:
        for i in range(1,num):
            answer = f1 + f0
            f0 = f1
            f1 = answer
    return answer

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(fibonacci(9))

2) 다른 풀이

: for 문을 이용하여 풀었지만, 훨씬 간단하게 풀었다.

def fibonacci(num):
    a, b = 0, 1
    for i in range(num):
        a, b = b, a+b
    return a

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(fibonacci(3))