[Python] 백준 풀기 24416 - 알고리즘 수업, 피보나치 수 1

파이썬 백준 24416번

브론즈1

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

24416번: 알고리즘 수업 - 피보나치 수 1

 

 

 

문제 보기

 

오랜만에 보아 친숙한듯 친숙하지 않은 피보나치 수.

 

 

 

문제 풀기

재귀함수를 사용하게 되면 지속적인 함수를 호출하는 과정을 거치면서 최종적으로 n = 1 을 터치하고 return 을 통해 다시 돌아오는 과정을 거치게 된다. 게다가 피보나치 수열의 특성상 n - 1 과 n - 2 를 재귀함수로 각각 다시 돌려야하는 비효율적이기까지..

동적 프로그램은 현재 계산의 결과가 다음 계산에도 영향을 미치는 fib_ls[i] = fib_ls[i - 1] + fib_ls[i - 2] 구조 때문에 그렇게 부르는것 같은데, 이 방법을 통해 각 계산 결과를 리스트에 저장을 하게되고 이 저장값들은 당연시 되게 다음 계산에 사용되기 때문에 재귀함수로 뺑뺑이 돌리는 것보다 훨씬 빠르고 효율적임을 확인할 수 있었다.

이 동적 구조를 작성하는 감각과 연습이 필요한것 같다.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnFibonacciByRecursion(num):
    global count_rec
    
    count_rec += 1                  # 다음에 나올 fnFibonacciByRecursion 를 위한 카운트.
    
    if num == 1 or num == 2:
        count_rec -= 1              # 다음에 fnFibonacciByRecursion 가 실행 되지 않기 때문에 빼줌.
        return 1
    else:
        num = fnFibonacciByRecursion(num - 1) + fnFibonacciByRecursion(num - 2)
        return num

def fnFibonacciByDynamic(num):
    global count_dyn
    
    fib_ls[1], fib_ls[2] = 1, 1
    
    for i in range(3, num + 1):
        count_dyn += 1              # for 문에 의한 반복 수행만 코드 실행 횟수로 본다.
        fib_ls[i] = fib_ls[i - 1] + fib_ls[i - 2]
    return fib_ls[num]


num = int(inputdata().strip())
fib_ls = [None for _ in range(num + 1)]
count_rec, count_dyn = 0, 0

fnFibonacciByRecursion(num)
fnFibonacciByDynamic(num)

print(count_rec + 1, count_dyn)     # fnFibonacciByRecursion(num) 실행시 처음 함수 시작으로 인한 횟수 1 더함.

결과 코드는 Python3 에서 시간 초과 걸리기에 PyPy3 로 제출함.