[Python] Dynamic Programing(Dp 알고리즘) - 피보나치 수열

피보나치 수열이란

수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. [위키백과]

이다!.

---

 

보통 피보나치 수열을 계산할 때 재귀로 많이 풀었는데, 재귀로 풀면 시간이 점점 증가하기 때문에 50이상은 구하기 힘들다.

이럴 때 쓸 수 있는게 동적 계획법, 즉 다이나믹 프로그래밍 이다.

 

 

동적계획법 (DP)

---

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. [위키백과]

 

 

동적계획법의 과정

---

1. 동적계획법은 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해서 문제를 해결하는 알고리즘입니다.

2. 문제를 쪼개서 정의할 수 있다면 동적 계획법을 쓸 수 있습니다. (ex 피보나치 f(3) = f(1) + f(2)

3. 그리고 이 결과를 기록하고 이용합니다. 

4. 결과를 기록하는 것을 메모이제이션(Memoization) 이라고 하고, 문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping Subproblem)라고 합니다!

 

 

 

피보나치 수열 - 동적계획법

---

 

구현의 방법은 다음과 같습니다.

1. 메모용 데이터를 만든다. 처음 값인 Fibo(1), Fibo(2) 는 각각 1씩 넣어서 저장해둔다.
2. Fibo(n) 을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.
3. Fibo(n) 을 처음 구했다면 메모에 그 값을 기록한다.

 

input = 50

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}


def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:
        return fibo_memo[n]

    nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
    fibo_memo[n] = nth_fibo
    return nth_fibo


print(fibo_dynamic_programming(input, memo))