동적 계획법(Dynamic Programming)이란 무엇인가?

동적 계획법(Dynamic Programming)

문제를 더 작은 단위의 문제로 분할하여 해결하는 분할 정복 알고리즘에 문제의 결과값을 캐싱하는 방법론이 합쳐진 문제해결 패러다임이다.

접근 방식에 따라 Top-Down, Bottom-Up 두가지 방식으로 구현된다.

Top-Down 접근법

큰 문제를 작은 문제로 분할하며 접근하는 방식이다.
대부분 재귀함수의 형태를 띈다.

using System;

class Program
{
    static int[] cache;

    static int fibo(int n)
    {
        if (cache[n] != 0)
            return cache[n];
        else if (n == 1 || n == 2)
            return cache[n] = 1;

        return cache[n] = fibo(n -2) + fibo(n - 1);
    }

    static void Main(string[] args)
    {
        string input = Console.ReadLine();

        if (int.TryParse(input, out int n) && n > 0)
        {
            cache = new int[n + 1];

            int output = fibo(n);

            Console.WriteLine(output);
        }
    }
}

작은 문제의 결과를 캐싱해두고 재사용하기 때문에 스택 오버플로우 걱정은 안해도 된다.

Bottom-Up 접근법

작은 문제를 우선 해결하여 큰 문제를 해결하는 접근 방식이다.
대부분 반복문의 형태를 띈다.

using System;

class Program
{
    static int[] cache;

    static int fibo(int n)
    {
        if (n == 1 || n == 2)
            return 1;

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

        return cache[n];
    }

    static void Main(string[] args)
    {
        string input = Console.ReadLine();

        if (int.TryParse(input, out int n) && n > 0)
        {
            cache = new int[n + 1];

            int output = fibo(n);

            Console.WriteLine(output);
        }
    }
}

캐싱 방법론

동적 계획법에 사용되는 두가지 캐싱 방법론이다.
Top-Down에선 메모이제이션, Bottom-Up에선 타뷸레이션이 사용된다.

메모이제이션(Memoization)

동적 계획법으로 문제를 해결할 때 Top-Down으로 접근할 경우 사용된다.
특징으로는 값이 필요할 때 계산하고 캐싱한다는 점이 있다.

static int[] cache;

static int fibo(int n)
{
	if (cache[n] != 0)
    	return cache[n];
    else if (n == 1 || n == 2)
    	return cache[n] = 1;

	return cache[n] = fibo(n -2) + fibo(n - 1);
}

위 피보나치 함수는 캐싱된 데이터가 있는지 우선적으로 확인하고 없는 경우 값을 계산하여 캐싱한다.

타뷸레이션(Tabulation)

동적 계획법으로 문제를 해결할 때 Bottom-Up으로 접근할 경우 사용된다.
특징으로는 값을 미리 계산해둔다는 점이 있다.

static int[] cache;

static int fibo(int n)
{
	if (n == 1 || n == 2)
    	return 1;

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

	return cache[n];
}

위 피보나치 함수는 문제의 최소 단위(위 코드에서는 n == 3인 경우)부터 계산하여 캐싱하고 최종 결과값을 도출한다.