EXCELSIOR

[Level1] 피보나치 수 (Fibonacci) 본문

Python/알고리즘_문제

[Level1] 피보나치 수 (Fibonacci)

Excelsior-JH 2016. 11. 11. 19:09

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))


Comments