[알고리즘] 다이나믹 프로그래밍

다이나믹 프로므래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

중복되는 연산을 줄이자 !!

비효율적인 피보나치 수열

피보나치 수열을 재귀함수로 구현하게 되면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

// 피보나치 함수를 재귀함수로 구현
int fibo (int x) {
    if (x == 1 || x == 2) {
        return 1;
    }
    return fibo(x - 1) + fibo(x - 2);
}

int main(void) {
    cout << fibo(4) << endl;
}

😥 f(n) 함수에서 n이 커지면 커질 수록 수행 시간이 기하급수적으로 늘어나게 된다.

f(6)에서는 f(3)가 3번, f(4)가 2번이나 호출됐다.
👉 이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효울적으로 해결할 수 없다.

피보나치 수열은 다음 조건을 만족한다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

💡 이 문제를 메모제이션 기법을 사용해서 해결해보자.

메모제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.

---

탑다운 방식

큰 문제를 해결하기 위해 작은 문제를 호출한다.

// 피보나치 수열 탑다운
#include <bits/stdc++.h>
using namespace std;

// 한 번 계산된 결과를 메모제이션(Memozation)하기 위한 배열 초기화
long long d[100];

// 피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
long long fibo(int x) {
    // 종료 조건 (1 혹은 2일 때 1을 반환)
    if (x == 1 || x == 2) {
        return 1;
    }

    // 이미 계산한 적 있는 문제라면 그대로 반환
    if (d[x] != 0) {
        return d[x];
    }
    // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x - 1) + fibo(x - 2);
    return d[x];
}

int main(void) {
    cout << fibo(50) << endl;
}

👉 위와 같은 방식은 노란 색으로 색칠된 노드만 방문한다❗

---

보텀업

작은 문제부터 차근차근 답을 도출한다.
👉 반복문 이용

// 피보나치 수열 보텀업
#include <bits/stdc++.h>
using namespace std;

// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
long long d[100];

int main(void) {
    // 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
    d[1] = 1;
    d[2] = 1;
    int n = 50; // 50번째 피보나치 수를 계산

    // 피보나치 함수를 반복문으로 구현 (보텀업 다이나믹 프로그래밍)
    for (int i = 3; i <=n; i++) {
        d[i] = d[i - 1] + d[i - 2];
    }
    cout << d[n] << endl;
}

💡 탑다운 방식보다는 보텀엄 방식으로 구현하는 것을 권장