8. C++ 동적프로그래밍, 재귀, Top Down, Bottom Up, 피보나치

* 개인 공부를 위하여 간단하게 정리한 것입니다. 

* 틀린 부분 지적은 늘 환영입니다.

 

일반적으로, 프로그래밍에서 피보나치 수열은 재귀함수를 통하여 구현합니다. 그러나 만약 a(n)의 피보나치 수열을 구할 때, 시간복잡도는 2^n이 되어 문제가 됩니다.

 

동적프로그래밍을 이용하여 피보나치 수열을 구하는 방법을 알아보겠습니다.

 

 

1. 피보나치 수열 (Fibonacci Sequence)

 

1, 1, 2, 3, 5, 8, 13, 21 ... 과 같은 형태로 나타나는 수열

 

1.1. 피보나치 수열의 점화실

 

a(n+2) = a(n+1) + a(n) (n >=3, a(1) = a(2) = 1)

 

 

2. 재귀함수 (Recursive Function)

 

a(1) = a(2) = 1

a(n) = a(n-1) + a(n-2)

if) n==5

a(5) = a(4) + a(3) = a(3) + a(2) + a(2) + a(1) = a(2) + a(1) + a(2) + a(2) + a(1) 

 

2.2. 코드

 

int fibo_rec(int n) {
    if (n <= 2)
        return 1;
    return fibo_rec(n - 1) + fibo_rec(n - 2);
}

 

3. 동적프로그래밍

3.1.1. Top Down 

 

한 번 구한 a(m)을 배열에 저장하여 다음 번 a(m) 시행에는 배열에 저장된 값을 사용합니다.

if) n== 5

a(5) = a(4) + a(3)

 -> a(4) = a(3) + a(2)

 -> a(3) = a(2) + a(1) ==> 저장

 --> a(4)에서 a(3)은 배열에 저장된 값, a(2)는 1임을 이용하여 a(4)를 구함 ==> 저장

 --> a(5)에서 a(4), a(3)은 배열에 저장된 값을 이용 

 

3.1.2. 코드

vector<long long> DP_topDown(100, 0);

int fibo_topDown(int n) {
    if (n == 1 || n == 2)
        return 1;
    if (DP_topDown[n] == 0) {
        return fibo_topDown(n - 1) + fibo_topDown(n - 2);
    }
    if (DP_topDown[n] != 0) {
        return DP_topDown[n];
    }

}

 

3.2.1. Bottom Up

 

a(n)을 위해 n크기(혹은 그 이상)의 배열을 선언하여 선언하고, 하나씩 채워 나가는 방식

 

if) n == 5 & B[5] 초기화 (B[5] : {0,0,0,0,0}

a(1), a(2) => 각각 B[0],b[1]에 저장 

a(3) = a(2) + a(1) => B[2]에 저장

a(4) = a(3) + a(2) => B[3]에 저장된 a(3)과 a(2) 이용하여 구함 => B[4]에 저장

a(5) = a(4) + a(3) => B[4], B[3]에 저장된 값을 이용

 

3.2.2. 코드

int fibo_bottomUp(int n) {
    vector<int> DP_bottomUp(n, 0);
    DP_bottomUp[0] = 1;
    DP_bottomUp[1] = 1;
    for (int i = 2; i < n; i++) {
        DP_bottomUp[i] = DP_bottomUp[i - 1] + DP_bottomUp[i - 2];
    }
    return DP_bottomUp[n - 1];
}

 

4. 전체코드

#include<iostream>
#include<vector>

using namespace std;

vector<long long> DP_topDown(100, 0);

int fibo_rec(int n) {
    if (n <= 2)
        return 1;
    return fibo_rec(n - 1) + fibo_rec(n - 2);
}

int fibo_topDown(int n) {
    if (n == 1 || n == 2)
        return 1;
    if (DP_topDown[n] == 0) {
        return fibo_topDown(n - 1) + fibo_topDown(n - 2);
    }
    if (DP_topDown[n] != 0) {
        return DP_topDown[n];
    }

}

int fibo_bottomUp(int n) {
    vector<int> DP_bottomUp(n, 0);
    DP_bottomUp[0] = 1;
    DP_bottomUp[1] = 1;
    for (int i = 2; i < n; i++) {
        DP_bottomUp[i] = DP_bottomUp[i - 1] + DP_bottomUp[i - 2];
    }
    return DP_bottomUp[n - 1];
}

int main() {
	cout << fibo_rec(5) << endl;
    cout << fibo_topDown(15) << endl;
    cout << fibo_bottomUp(15) << endl;
    return 0;
}

동적프로그래밍, 재귀, Top Down, Bottom Up, 피보나치