동적계획법

최규진·2025년 4월 7일

학습목표

동적계획법을 이해하고, 점화식을 세워 동적계획법 문제에 적용할 수 있다.

동적계획법이란?

이미 계산한 값을 활용하지 않고, 중복된 연산을 하는 경우가 허다합니다. 이를 극복하는 알고리즘이 바로 동적계획법입니다.
이미 저희에게 친숙한 피보나치 수를 한 번 살펴보겠습니다.

https://www.acmicpc.net/problem/10870
피보나치 수 5를 살펴보겠습니다.
재귀함수를 이용했다면, 다음과 같이 문제를 풀었을 것 입니다.

#include <iostream>

using namespace std;

int n;

int finbonacci(int x) {
    if (x == 0)
        return 0;
    if (x == 1)
        return 1;
    return finbonacci(x - 1) + finbonacci(x - 2);
}

int main(void) {
    cin >> n;
    cout << finbonacci(n);
    return 0;
}

시간복잡도를 확인해보겠습니다.

f(4)의 함수 호출 과정입니다.
이렇게 되면 시간복잡도가 $O(2^n)$ 이 됩니다.
n이 커지면 커질 수록 많은 연산이 불필요하게 중복되기 때문입니다.

이 중복을 피하기 위해서는 어떻게 하면 될까요?
크게 두 가지 방법을 볼 수 있습니다.

연산 결과를 기록하기

#include <iostream>

using namespace std;

long long dp[100] = {0, 1,};

long long fibonacci(int n) {
	if (n <= 1) {
		return n;
	} 
    if (dp[n] == 0)
		dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
	return dp[n];
}

int main(void) {
	int n;
	cin >> n;
	cout << fibonacci(n);
}

위 dp배열에는 계산된 피보나치 값이 저장됩니다. 이미 값이 저장되어 있으면 계산을 할 필요가 없어, 배열의 값을 반환해주고, 저장되지 않았다면 계산 후 dp에 넣어주어 같은 계산을 하지 않도록 합니다.

계산한 결과로 연산을 수행하기

#include <iostream>

using namespace std;

long long dp[100];
int n;

int main(void) {
    cin >> n;

    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    cout << dp[n];

    return 0;
}

피보나치 수를 계산하는 데에 필요한 수는 직전과 이전 두 가지 뿐입니다. 이를 이용해 차근차근 쌓아 올라가는 방법입니다. 우리가 실제 피보나치 함수를 손으로 직접 계산하는 것과 비슷한 방법으로 진행됩니다.

이 동적계획법에서는 두가지 접근방법이 사용될 수 있고, 접근 방법에 따라서 각각에 알맞는 기법이 사용됩니다.

하향식 접근법 : Top-down appraoch 큰 문제를 부분문제들로 쪼개어가며 해결하는 방식입니다. 5번째 피보나치 수를 구하기 위해 3번째 피보나치 수와 4번째 피보나치 수를 구하는 것으로 쪼개는 것과 같은 사고방식입니다. 전에 살펴보았던 1. 연산 결과를 기록하기의 방법입니다.
따라서 보통 재귀로 구현됩니다. 여기서, 중복되는 계산을 피하기 위해 값을 계산했다면 가져다 쓰고, 새로운 계산을 했다면 나중을 위해 메모해 둡니다. 이전의 피보나치의 예시에서 dp배열에 계산 결과를 메모했었죠? 이렇게 한번 계산 한 값을 메모하는 기법을 메모이제이션(memoization)이라고 합니다.
이름 그대로 “적어놓기” 라는 뜻입니다.

상향식 접근법 : Bottom-up appraoch 큰 문제를 쪼개는 탑다운과는 반대로, 기초가 되는 가장 작은 부분문제부터 시작해 큰 문제에 대한 최적해를 만들어 나가는 방식입니다. 0번째 피보나치수와 1번째 피보나치수를 이용해 2번째 피보나치수를 구하고, 1번째와 2번째를 이용해 3번째를 만들고 … n-2번째와 n-1번째를 이용해 n번째를 만들어 답을 구하는 방식입니다. 2. 계산한 결과로 다음 연산을 수행하기와 같은 방법이며,
따라서 보통 반복문으로 구현하게 됩니다. 다음 계산을 하기 위해 이전의 계산 결과가 필요하고, 어딘가에 저장해 두어야 하겠죠? 피보나치의 예시에서는 이전 두개의 결과만이 필요하다는 것이 확실하기에 두개의 변수로 충분했습니다.

뭐가 더 나은가?

그럼 두 방법중에 어떤 방법이 좋은 방법일까요?

당연하게도, 문제 상황에 따라 다릅니다.

탑다운의 방식의 장점은 큰 문제의 최적해에 필요한 부분문제만을 구해내면 된다는 것입니다.

바텀업의 경우, 큰 문제 이전의 모든 부분문제를 구해내야 하기에 불필요한 계산을 더 하게 될수도 있죠.

그럼 피보나치와 같이 큰 문제의 최적해가 어차피 모든 부분문제를 구해야 찾아지는 구조라면, 둘의 차이가 없는걸까요?

탑다운 방식의 단점은 그 구현 방법인 “재귀” 자체에 있습니다. 프로그램에서는 함수 자체를 실행하는 데에 따른 오버헤드가 발생하게 됩니다. 함수를 실행할 때 함수 호출과 값을 반환하는 과정에서 메모리와 시간을 소모하게 되는데, 호출 횟수가 적다면 별 의미 없지만, 재귀로 인해 아주 많은 호출이 일어나게 될 경우 아주 큰 차이가 발생하게 될 수 있습니다.

실제로 바텀업 방식을 통해 반복문으로 구현하면 맞았습니다를 받게 되지만, 탑다운 방식을 통해 재귀로 구현하면 메모리 초과를 받게 되는 경우가 있습니다.

정리하며

오늘은 동적계획법에 대해 알아보았습니다. 동적계획법은 중복 계산을 줄일 수 있고, 효율적인 시간 복잡도를 가질 수 있다는 장점이 있지만, 메모리 사용량을 잘 생각해야하는 알고리즘입니다.

최규진

나는 개발자입니다.

이전 포스트

Unsupported class file 오류 해결하기

다음 포스트

동적계획법

학습목표