다이나믹 프로그래밍(Dynamic Programming)

- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

 

- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록

 

- 탑다운(top-down) or 보텀업(bottom-up) 방식

 

다음 조건을 만족할 때 사용 가능

• 최적 부분 구조 - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결
• 중복되는 부분 문제 - 동일한 작은 문제를 반복적으로 해결

 

예시) 피보나치 수 구하기

 

피보나치는 점화식(인접한 항들 사이의 관계식)으로, 현재의 항을 이전의 항에 대한 식으로 표현 가능

 

출처 : https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

 

피보나치 수열을 아래와 같은 방법을 활용하여 구할 수 있다.

 

#include <iostream>

using namespace std;

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

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

그러나 위의 방법은 지수 시간 복잡도를 가지게 된다.

 

왜냐하면 N의 수가 증가하면 그만큼 함수 호출도 중복되기 때문이다. (특히 f(2)나 f(1)이 많이 중복된다)

 

위와 같이 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다.

 

피보나치 수는 아래를 만족한다.

 

 큰 수를 작은 수로 나눌 수 있다.

 동일한 작은 문제를 반복적으로 해결한다.

 

때문에 다이나믹 프로그래밍 기법을 사용하여 문제를 해결할 수 있다.

 

탑다운(top-down) or 보텀업(bottom-up) 방식으로 다이나믹 프로그래밍 구현

 

탑다운 방법 - 하향식

메모이제이션(Memoization)

 

한 번 계산한 결과를 메모리 공간에 메모하는 기법 - 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미

같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.

 

값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.

 

보통, 재귀적 방법으로 해결

 

메모이제이션을 사용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N)

 

#include <iostream>

using namespace std;

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

// 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
long long fibo(int x) {
    cout << "f(" << 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) << '\n';
}

위를 보면 d[100]의 배열을 생성해 놓고 그곳에 계산 결과를 저장해 불러오는 것을 확인할 수 있다.

 

물론 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 

 

따라서 재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다.

 

보텀업 방법 - 상향식

 

위 탑다운 방식은, 큰 문제를 해결하기 위해 작은 문제를 호출하였다.

 

보텀업 방식은 아래서부터 문제를 해결하는 것으로, 보통, 반복문으로 해결한다.

 

다이나믹 프로그래밍의 전형적인 형태가 보텀업

 

결과 저장용 리스트는 DP 테이블이라고 부른다.

 

#include <iostream>

using namespace std;

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

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

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

 

 

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.

 

탑다운 - 메모이제이션

(메모이제이션 : 이전에 계산된 결과를 일시적으로 기록해 놓는 개념)

 

보텀업 - DP 테이블

 

다이나믹 프로그래밍 vs 분할 정복(예시, 퀵 정렬)

공통점

모두 최적 부분 구조를 가질 때 사용 가능

(큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황)

 

차이점

부분 문제의 중복

다이나믹 프로그래밍 : 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복

분할 정복 : 동일한 부분 문제가 반복적으로 계산되지 않음.

 

내용 및 코드 참고

www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5