125. 24416(알고리즘 수업 - 피보나치 수 1)

본 코드는 pypy3로 제출해야합니다.

n = int(input())
cntFib = 0
cntFib2 = 0
memo = [0 for i in range(100)]   


def fib(n):
    global cntFib    
    if n == 1 or n == 2:
        cntFib += 1       
        return 1
    else:
        return fib(n-1)+fib(n-2)

def fibonacci(n):
    global cntFib2
    
    if memo[n] > 0:
        cntFib2 += 1
        return memo[n]
    
    if n <= 1:      
        memo[n] = n
        return memo[n]
    
    else:
        memo[n] = fibonacci(n-1) + fibonacci(n-2)
        return memo[n]       
    
fib(n)
fibonacci(n)
print(cntFib, cntFib2)

문제요약

재귀함수와 동적프로그래밍을 이용하여 호출횟수를 출력하라.

설명

동적프로그래밍의 개념은 아래를 참고하자.

https://smhope.tistory.com/328?category=1056187 

동적프로그래밍(Dynamic Programming)

 

주의점

Down - Top 방식을 사용하면 Top - Down 보다 cnt를 한번 더 증가 시킴.

n = int(input())
cntFib = 0
cntFib2 = -1

def fib(n):
    global cntFib
    if n == 1 or n == 2:
        cntFib += 1
        return 1
    else:
        return fib(n-1)+fib(n-2)

def fibonacci(n):
    global cntFib2
    if n <= 1:               
        return n   
    first = 0
    second = 1
            
    for _ in range(0, n-1):
        tmp = first + second
        first = second
        second = tmp
        cntFib2 += 1
    return tmp
            
    
    
fib(n)
fibonacci(n)
print(cntFib, cntFib2)