Algorithm, Python, C++ 피보나치 수열 (동적 계획법)

동적 계획법 / 개념&활용 / 예시(피보나치 수열)

그나저나 c++ 세상 오랜만... 다 잊어버렸다 미쳐 진짜

---

동적 계획법(Dynamic Programming, DP)

- 큰 문제를 해결하기 위해 작은 부분 문제를 해결하고 그 결과를 저장, 재활용하여 전체 문제를 해결.

- 최적화 문제, 최단 경로 문제

- 핵심은 메모이제이션(Memoization) : 작은 부분 문제들의 해결 값을 저장 -> 재사용하는 구조

- 특징 : 중복되는 부분 문제들의 해결을 효율적으로 처리하여 전체적인 계산량을 감소시킴

1. 최적 부분 구조(Optimal Substructure)

큰 문제의 최적해가 작은 문제들의 최적해로 구성되어 있어야 한다.

 

2. 중복 부분 문제(Overlapping Subproblems)

동일한 부분 문제가 여러 번 반복되어 해결되어야 한다.

- 구현 : 탑다운(Top-Down)과 바텀업(Bottom-Up) 두 가지 방식

Top-down : 재귀적인 방법으로 작은 문제들을 해결, 그 결과를 메모제이션하여 활용

Bottom-Up : 작은 문제부터 시작하여 전체 문제를 해결하는 방법으로, 일반적으로 반복문 사용.

- 피보나치 수열

Python↓

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

def fibonacci_memoization(n, memo={}):
    if n <= 1:
        return n
    elif n not in memo:
        memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
    return memo[n]

# 피보나치 수열의 10번째 항까지 출력
for i in range(10):
    print(fibonacci_recursive(i), end=' ')
print()

for i in range(10):
    print(fibonacci_memoization(i), end=' ')

C++↓

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<int, int> memo;

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

int fibonacci_memoization(int n) {
    if (n <= 1) {
        return n;
    } else if (memo.find(n) == memo.end()) {
        memo[n] = fibonacci_memoization(n-1) + fibonacci_memoization(n-2);
    }
    return memo[n];
}

int main() {
    // 피보나치 수열의 10번째 항까지 출력
    for (int i = 0; i < 10; ++i) {
        cout << fibonacci_recursive(i) << ' ';
    }
    cout << endl;

    for (int i = 0; i < 10; ++i) {
        cout << fibonacci_memoization(i) << ' ';
    }
    cout << endl;

    return 0;
}