[백준] [Python] 10870번: 피보나치 수 5

 

 

[ 문제 ]

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

[ 조건 ]

<입력>
첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

<출력>
첫째 줄에 n번째 피보자니 수를 출력한다.

---

[ 풀이 ]

# My solution
memo = {
        0 : 0,
        1 : 1
    }    #1

def fib(n) :    #2
    if n in memo :
        return memo[n]
    else :
        output = fib(n-1) + fib(n-2)
        memo[n] = output
        return output

n = int(input())    #3
print(fib(n))

실행결과

10    # 입력값
55    # 출력값

처음에 정답을 받은 풀이는 아래와 같다.

# My solution
def fib(n) :
    if n == 0 :
        return 0
    elif n == 1 :
        return 1
    else :
        output = fib(n-1) + fib(n-2)
        return(output)

n = int(input())
print(fib(n))

문제의 조건에서 입력받는 n이 20보다 작다는 조건이 있었기 때문에 당장 문제를 해결하는 데 큰 문제는 없었지만,
위와 같은 형태의 코드는 숫자가 커지면 커질수록 함수를 반복해야 하는 횟수가 기하급수적으로 많아지기 때문에 시간이 굉장히 오래 걸린다.

 

파이썬의 내장 모듈 중 하나인 time모듈을 활용하여 코드가 작동한 시간을 확인하여 보자.

 

time모듈의 time()함수는 현재의 유닉스 시간을 알려주는 함수이다.

'유닉스 시간'은 시각을 나타내는 방식 중 하나로, '1970년 1월 1일 00:00:00 협정 세계시' 로부터 경과한 시간을 초로 환산하여 정수로 나타낸 것이다.(https://ko.wikipedia.org/wiki/유닉스_시간)

import time
start = time.time()

def fib(n) :
    if n == 0 :
        return 0
    elif n == 1 :
        return 1
    else :
        output = fib(n-1) + fib(n-2)
        return(output)

n = int(input())
print(fib(n))

end = time.time()
print('실행시간:', end-start)

실행결과

40    # 입력값
102334155    # 출력값
실행시간: 60.636770725250244

숫자 40을 입력했음에도 60초가 넘는 시간이 걸렸다.
이로써 숫자가 증가하면 급격하게 실행시간이 늘어남을 확인할 수 있다.

 

하지만 본문의 풀이를 이용하여 문제를 풀면 다른 결과를 확인할 수 있다.

import time
start = time.time()

memo = {
        0 : 0,
        1 : 1
    }

def fib(n) :
    if n in memo :
        return memo[n]
    else :
        output = fib(n-1) + fib(n-2)
        memo[n] = output
        return output

n = int(input())
print(fib(n))

end = time.time()
print('실행시간:', end-start)

실행결과

40    # 입력값
102334155    # 출력값
실행시간: 1.7206509113311768

숫자가 커져도 별다른 시간의 차이가 나타나지 않는다.

 

"재귀함수를 사용할 때는 메모화를 활용하여 시간을 줄이도록 하자"

---

#1

피보나치 수를 해결하기 위해서 재귀함수를 사용할 것이기 때문에 사전에 메모화를 할 딕셔너리(memo)를 하나 생성한다.

 

메모화를 하는 이유는 불필요하게 반복되는 함수의 사용을 막아서 빠르게 값을 리턴하기 위함이다.

 

피보나치 수에서 0번째 항과 1번째 항은 각각 0과 1로 정해져 있기 때문에 미리 memo에 값을 입력해둔다.

 

 

#2

def를 이용하여 피보나치 함수를 생성한다.

 

이때 if-else 조건문을 사용하여
만일 입력받은 n이 메모화된 값이면(memo 안에 값이 존재한다면) 바로 메모화된 값을 출력하도록 한다.

 

만일 메모화되지 않은 값이라면 본래의 피보나치 수 공식대로 입력받은 숫자(n)의 바로 앞 두 항(n-1, n-2)의 합을 리턴한다.

이때 얻은 새로운 값은 메모화 해주도록 한다.

 

 

#3

n을 입력받은 후, 위에서 생성한 피보나치 함수에 n을 대입하여 실행한다.

 

---

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5