[백준/2747] 피보나치 수 with 동적 계획법

이 내용은 알고리즘 수강 시간에 배웠던 내용이라 눈치를 챌 수 있었다.

def fibo(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        result = fibo(n-1) + fibo(n-2)
        return result

print(fibo(int(input())))

단순히 이렇게 재귀형식으로 피보나치 수열을 만들 수 있지만, 이렇게 되면 

• fibo(10)을 구하기 위해 fibo(9)와 fibo(8)을 구해야 한다.
• fibo(9)를 구한 다음, fibo(8)을 구하려면 다시 처음부터 구해야 한다.
• 따라서 시간 복잡도는 T(n) = T(n-1) + T(n-2)
• 결국 T(n) >= 2^n/2T(1)으로, 지수 시간이 걸리게 된다. 😱

---

이를 해결하기 위해 동적 계획 알고리즘을 사용한다. 

동적계획법의 특징은 큰 문제를 작은 문제로 나눠서, 작은 문제가 곧 큰 문제의 정답이 된다는 특징이 있다.

피보나치 수열도 마찬가지이다. 앞서 재귀함수에서는 fibo(10)을 구하기 위해 fibo(9)와 fibo(8)을, fibo(8)을 구하기 위해 ...

이렇게 작은 문제까지 다시 더해줘야 했다. 하지만 동적계획법을 사용해서 fibo(x) 값을 한번 구한 뒤, 배열 Fibo에 저장해주면

fibo함수가 호출될 때 마다 적어도 한 값은 배열 Fibo에 기록이 된다.

따라서 시간 복잡도를 T(n) = O(n)으로, 피보나치 수열의 깊이 만큼으로 줄일 수 있다!

---

피보나치 수열의 동적계획 구현은 의외로 간단하다.

값을 저장할 list를 생성하고, 한번 호출된 값들을 저장해주면 된다.

def fibo(n,F):
    if n < 3 :
        return F[n]
    else:
        F[n] = fibo(n-1, F) + fibo(n-2, F)
        return F[n]

F = [0]*46
F[1] = 1
F[2] = 1
print(fibo(int(input()), F))

어라리 여전히 시간초과 발생....

이 문제는 재귀가 아닌 형태로 피보나치를 구현하라는 의도 같아서 아래와 같이 코드를 완전히 바꾸었다.

---

def fibo(n):
    F = [0] * 46
    F[1] = 1
    F[2] = 1
    
    for i in range(2, n+1):
        F[i] = F[i-1] + F[i-2]
    return F[n]

print(fibo(int(input())))

문제에서 n은 45까지라고 지정해주었기 때문에 배열은 F[0] * 46 만큼 만들어주었다.

for문을 통해 피보나치 수열을 재귀식이 아닌 배열식으로 저장해주는 형태로 구현 완료!