참고 영상
https://youtu.be/rWbjQphRE9A
https://www.youtube.com/watch?v=VcCkPrGaKrs

다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 메모리를 적절히 사용하여 시간복잡도를 비약적으로 단축시킬 수 있는 방법이다. 핵심 원리는 이미 계산된 결과를 별도의 메모리 공간에 저장하여 다시 계산하지 않도록 하는 것이다. 다이나믹 프로그래밍은 일반적으로 하향식(top-down) 또는 상향식(bottom-up)으로 구현된다.

cf) 다이나믹 프로그래밍은 동적 계획법이라고도 부르는데, 일반적인 프로그래밍 분야에서 동적(dynamic)이란 어떤 의미를 가질까?
자료구조에서 동적 할당 (dynamic allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. 반면에, 다이나믹 프로그래밍에서 다이나믹은 별다른 의미 없이 사용된 단어이다.

다이나믹 프로그래밍의 조건

다이나믹 프로그래밍은 문제가 다음 조건을 만족시킬 때 사용할 수 있다.

1. 최적 부분 구조 (Optimal substructure)
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

2. 중복되는 부분 문제 (Overlapping subproblem)
동일한 작은 문제를 반복적으로 해결한다.

예시: 피보나치 수열

피보나치 수열은 첫째, 둘째 항이 1이고 그 뒤의 모든 항은 바로 앞의 두 항의 합으로 이루어진 수열이다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

점화식이란 인접한 항들 사이의 관계식을 의미하는데, 피보나치 수열을 점화식으로 표현하면 다음과 같다.

$a_1 = 1$, $a_2 = 1$
$a_n = a_{n-1} + a_{n-2}\ (n \geq 3)$

일단, 재귀 함수를 사용하여 피보나치 수열을 구해보자.

#include <iostream>
using namespace std;

int fibo(int x){
	if(x == 1 || x == 2){
		return 1;
	}
	return fibo(x - 1) + fibo(x - 2);
}

int main() {
	for(int i = 1; i <= 11; i++)
		cout << fibo(i) << " ";
	cout << "\n";
    
    // 실행 결과: 1 1 2 3 5 8 13 21 34 55 89

    return 0;
}

시간복잡도 분석

단순 재귀 호출로 피보나치 수열을 구하면 O(2^n) 의 시간복잡도를 갖는다. F(2)와 F(3)처럼 동일한 부분 문제가 중복해서 재귀 호출되기 때문에, 입력 크기가 조금만 커져도 시간이 매우 오래 걸린다. 실제로 F(30)을 계산하려면 약 10억가량의 연산을 수행해야 하며, F(100)을 구하는 건 거의 불가능에 가깝다. 이를 개선하기 위한 방법이 다이나믹 프로그래밍이다.

메모이제이션 (Memoization)

메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나로서, 한 번 계산한 결과를 메모리 공간에 메모해두는 기법이다.

• 같은 문제를 다시 호출하면, 메모리에 저장해둔 결과를 그대로 가져온다.
• 값을 기록해놓는다는 점에서 캐싱(Caching)이라고도 부른다.

cf) 넓은 의미로 생각하면, 이전에 계산된 결과를 일시적으로 기록해 놓는다는 개념이다. 따라서 메모이제이션은 다이나믹 프로그래밍에만 국한된 개념이 아니다. 한번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍에는 활용하지 않을 수도 있다.

상향식 (bottom-up) vs. 하향식 (top-down)

상향식 (bottom-up)

아래쪽에서부터 작은 문제들을 하나씩 해결해 나가면서 최종적으로 큰 문제의 해를 구한다. 프로그래밍 언어에서는 반복문을 사용해서 구현한다. 다이나믹 프로그래밍의 전형적인 방식이며, 부분해의 결과를 임시적으로 저장하는 배열을 DP 테이블이라고 부른다.

#include <iostream>
using namespace std;

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

int main() {
    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] << '\n'; // 12586269025

	return 0;
}

하향식 (top-down)

큰 문제를 작은 문제로 나눠서 작은 문제들의 해를 '재귀적으로' 구하고, 이를 취합하여 큰 문제의 해를 구한다. 한 번 계산된 결과를 기억하기 위해서 메모이제이션 기법을 이용한다.

#include <iostream>
using namespace std;

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

// 재귀 호출로 구현 (하향식 다이나믹 프로그래밍)
long long fibo(int x) {
    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) {
	// 50번째 피보나치 수 계산
    cout << fibo(50) << '\n'; // 12586269025

	return 0;
}

개선된 시간복잡도

검은 부분은 다시 호출되지 않으며, 노란 부분은 테이블에 저장된 결과를 반환하는 부분이다. 처음에 F(2), F(3)을 구할 때는 재귀 호출을 하겠지만, 다시 구할 때는 그 이하의 숫자들을 재귀 호출하지 않고 배열에 저장된 값을 바로 이용한다! 따라서 O(2^n)이었던 시간복잡도는 O(n)으로 단축된다!

DP vs. 분할정복 알고리즘

다이나믹 프로그래밍과 분할정복 알고리즘은 모두 최적 부분 구조를 가질 때 사용할 수 있다. 즉, 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황일 때 쓰인다.

하지만, 다이나믹 프로그래밍은 각 부분 문제들이 독립적이지 않으며, 중복되는 부분 문제가 존재한다. 그리고 주로 점화식에 따라 작은 문제부터 하나씩 해결해나가면서 상향식으로 최종적인 해를 구한다.

반면에, 분할정복 알고리즘은 각 부분 문제가 독립적이고, 동일한 부분 문제가 반복적으로 계산되지 않는다. 그리고 큰 문제를 작은 문제로 분할하여 하향식으로 부분해를 구하고 이를 다시 취합하여 최종적인 해를 구한다.

분할정복 알고리즘의 대표적인 예시인 퀵 정렬을 생각해보자. 피벗을 기준으로 분할된 각 부분 리스트는 독립적으로 퀵 정렬을 수행한다. 그리고 한 번 분할이 완료될 때마다 결정된 피벗의 위치는 바뀌지 않는다. 즉, 부분 문제가 중복되지 않는다.

DP vs. 그리디 알고리즘

매 단계마다 현재 최적이라고 판단되는 것만 근시안적으로 선택하는 그리디 알고리즘은 오직 현재의 최대 만족만을 추구하기 때문에 전체적인 최적해는 보장하지 못하는 경우가 많다. 따라서, 단순히 가장 좋아보이는 것만 반복적으로 선택해도 최적의 해를 구할 수 있는지 그 정당성을 분석하는 게 중요하다.

반면에, 다이나믹 프로그래밍은 작은 문제에 대한 모든 가능성을 고려하여 다음 크기의 문제에 대한 최적해를 구하기 때문에 항상 최적의 결과를 얻을 수 있다.

다이나믹 프로그래밍 문제에 접근하는 방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 게 중요하다. 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토하고, 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해보자.

일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (하향식 접근)
작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 다이나믹 프로그래밍 방식으로 코드를 개선하면 된다.

일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다고 한다.

다이나믹 프로그래밍 적용 단계

1. 문제의 특성을 분석하여 최적 부분 구조가 성립하는지 확인한다.
2. 주어진 문제에 대해 최적해를 제공하는 점화식을 도출한다.
3. 가장 작은 부분 문제부터 점화식의 해를 구한 뒤 이를 테이블에 저장한다.
4. 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 입력 크기가 큰 상위 문제의 해를 구한다. (상향식)