동적 프로그래밍

미국의 응용수학자 리처드 E. 벨만이 제시한 최적화 이론의 한 갈래. 현대에는 그 의미가 확장되어 문제 풀이 기법 혹은 최적화 기법으로 인식된다.

기본적으로 동적 프로그래밍은 최적 제어 문제를 해결하기 위해서 고안된 방법이다.

상태기반의 문제를 재귀적으로 해석하는 방법은 너무나도 일반화 하기 쉬운 강력한 방법이었다. 이 문제를 최적제어 문제에만 쓰기 아까웠던 벨만은 다른 문제에도 사용하기 시작하였고 최적 경로, 그래프 탐색 문제등을 시작으로 동적 프로그래밍의 사상 아래에서 해결될 수 있음을 보였다.

이와 관련된 대표적인 예제는 동적 프로그래밍의 방법을 적용하여 피보나치 수열을 최적화 하는 문제가 있다. 아래의 코드는 Dictionary<int, int[]> 형태의 자료구조에 계산 값을 저장한 뒤, 중복된 계산식이 호출되면 해당 자료구조에서 이전에 계산된 값을 확인 후, 계산 값을 반환하여 불필요한 계산삽질을 처리하지 않게 한다.

Dictionary<int, int[]> dicFibo = new Dictionary<int, int[]>();

public int[] Getfibonacci(int n)
{
    if (n == 0)
    {
        if (!dicFibo.ContainsKey(0))
            dicFibo.Add(0, new int[] { 1, 0 });

        return new int[] { 1, 0 };
    }
    else if (n == 1)
    {
        if (!dicFibo.ContainsKey(1))
            dicFibo.Add(1, new int[] { 0, 1 });

        return new int[] { 0, 1 };
    }
    else
    {
        if (dicFibo.ContainsKey(n))
        {
            return dicFibo[n];
        }
        else
        {
            dicFibo[n] = new int[] { Getfibonacci(n - 1)[0] + Getfibonacci(n - 2)[0] , Getfibonacci(n - 1)[1] + Getfibonacci(n - 2)[1] };
            return dicFibo[n];
        }
    }
}

그의 자서전에 따르면 공군놈들이 연구 이름을 '의사 결정 프로세스'라고 재미없게 지으니까 좆같이 굴길래 '다이나믹 프로그래밍' 이라는 간지나는 이름을 붙였더니 좋아했다고 한다.[1]

보통은 코딩 새싹반 C나 C++을 배울때 피보나치 수열을 최적화하면서 처음 접하게 된다.

재귀함수나 반복문으로 구현한다.