[백준 10870] 피보나치 수 계산 - 재귀 / DP

해당 문제는 재귀 카테고리에 있어서 재귀함수로 풀었다. 

바로 전 문제가 팩토리얼 문제여서 재귀로는 쉽게 풀었다.

def fibo(n=int(input()), i=1):
    if n>2:
        return fibo(n-1) + fibo(n-2)
    return 0 if n==0 else 1

print(fibo())

 

그리고 다른 코드를 구경(?)하는데 변수를 dp로 설정했더라.

알진 못해도 들어본 적은 있어서 바로 검색해봤다.

DP는 동적계획법 (Dynamic Programming)으로 상향식 접근법이며 실행시간이 현저히 줄어든다는 장점이 있다.

이전에 계산한 값을 메모리에 저장해 다시 계산하지 않도록 하는 Memoization 기법을 사용한다.

 

n = int(input())
dp = [j for j in range(n+1)]
for i in range(2,n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n])

 

DP로 피보나치 계산을 한 코드다.

함수를 반복적으로 불러올 필요 없이 리스트에 바로바로 저장해 마지막 값만 반환하면 된다.

최적화 문제 해결시 유용한 알고리즘이라고 할 수 있다.