백준 2748 파이썬(DP)

피보나치 수열을 구하는 대표적은 다이나믹 프로그래밍 문제이다.

그러나 이번 문제는 단순히 문제를 해결하는 것 뿐만 아니라 더 빨리 효율적으로 풀 수 있는 알고리즘을 물어보고 있다.

문제의 답은 반복문 또는 메모이제이션을 이용해서 풀면 된다.

(메모이제이션을 이용한 코드는 아래 있다.)

# 반복문으로 푼 피보나치

n = int(input())
dp = [0]*100
dp[1] = 1
for i in range(2,n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

---

이번 기회에 피보나치 수열을 구하는데 사용되는 3가지 방법에 대해서 정리해보았다.

반복문, 재귀, 메모이제이션 총 세가지 방법으로 피보나치 수열을 풀 수 있지만 각각 시간복잡도, 메모리를 사용하는 정도가 다르다.

 

1. 반복문

코드는 위에 있고

총 n번의 연산을 한다는 것을 알 수 있다. 시간복잡도 O(N)

10번째 피보나치 수열을 구하려면 반복문이 10번 돈다.

세가지 방법중 가장 빠른 알고리즘이다.

 

2. 재귀

# 재귀방법으로 푼 피보나치
# 시간초과

n = int(input())
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(n))

우선 재귀함수는 반드시 탈출조건(base case)을 설정해주어야 하는데 이 문제에서는 n이 0 또는 1이 되는 경우다.

 

재귀방법으로 이 문제를 풀게되면 시간초과가 뜨게 된다.

즉 반복문으로 풀었을때보다 시간복잡도가 더 크다는 말이다.

재귀함수의 시간복잡도는 O(N^2)으로 지수함수를 따른다.

n이 1이 아닌 이상 함수를 한번 부를때마다 2번씩 재귀적으로 호출하기 때문에 연산횟수가 지수함수 모양으로 증가한다.

 

3. 메모이제이션(Memoization)

# memoization을 이용한 피보나치 수열
# 하향식
# 시간복잡도 O(N)
memo = {}
def fibo_memo(x):
    if x == 1 or x == 2:
        memo[x] = 1
        return memo[x]
    elif x in memo:
        return memo[x]
    else:
        memo[x] = fibo_memo(x-1) + fibo_memo(x-2)
        return memo[x]

메모이제이션 방법은 memo라는 딕셔너리를 이용해서 풀어주었다.

이미 계산한 값은 기억(memorize)해서 연산을 다시 하지 않고 바로 불러온다는 아이디어다.

 

얼핏보면 재귀함수와 같이 자기자신을 반복적으로 호출하므로 시간복잡도가 클 것 같지만 이미 계산한 값은 더이상 계산하지 않고 그냥 불러오기만 하면 되기 때문에 재귀함수보다 연산시간이 더 짧다.

따라서 시간복잡도는 N(O)로 반복문을 사용할때와 같다.