동적 프로그래밍_{(r30 편집)}

[[분류:수학]]
[[분류:떡밥위키 학문 프로젝트]]
[include(틀:프로젝트 문서, 프로젝트=떡밥위키 학문 프로젝트)]

[목차]
[clearfix]
== 개요 ==
미국의 응용수학자 리처드 E. 벨만이 제시한 최적화 이론의 한 갈래. 현대에는 그 의미가 확장되어 문제 풀이 기법 혹은 최적화 기법으로 인식된다.
== 상세 ==
> Divide & Conquer, Overlapping Subproblem

=== 최적제어에서의 동적 프로그래밍 ===
기본적으로 동적 프로그래밍은 최적 제어 문제를 해결하기 위해서 고안된 방법이다. 특히나 이산 시간(discrete time) 제어 문제에 적용하기 위한 방법으로 시작한다. 최적제어는 어떤 시스템의 상태 [math(x(t))]와 현재의 입력 [math(u(t))]을 기반으로 계산되는 비용 [math(J(t))]을 최소화 하는 문제상황을 말한다. 벨만은 이 문제를 해결하기 위해서 핵심 개념을 제시하는데 이것이 바로 '''최적성의 원리'''이다. 최적성의 원리란 별로 어렵지 않다. 어떤 문제에 대한 최적의 경로(=비용을 최소화 하는)가 존재할때, 그 하위 경로 역시 최적이어야 한다라는 의미이다. 때문에 동적 프로그래밍은 문제를 전체적으로 한 번에 푸는 것이 아니라, 문제를 시간적으로 나누어 각 시점마다 최적의 결정을 순차적으로 내려가는 방식으로 접근한다.
=== 컴퓨터 과학에서의 동적 프로그래밍 ===
상태기반의 문제를 재귀적으로 해석하는 방법은 너무나도 일반화 하기 쉬운 강력한 방법이었다. 이 문제를 최적제어 문제에만 쓰기 아까웠던 사람들은 다른 문제에도 사용하기 시작하였고 최적 경로, 그래프 탐색 문제등을 시작으로 동적 프로그래밍의 사상 아래에서 해결될 수 있음을 보였다.

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

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

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

재귀함수나 반복문으로 구현한다. 재귀로 구현할 때 depth가 너무 깊어지면 저지 사이트에서 돌리다가 메모리 초과! 가 뜰 수도 있으니 주의하자. 짱구를 잘만 굴리면 flatten할 수 있는 케이스가 많이 있다.

요약

문서 편집을 저장하면 당신은 기여한 내용을 CC BY-NC-SA 2.0 KR으로 배포하고 기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다. 이 동의는 철회할 수 없습니다.

비로그인 상태로 편집합니다. 로그인하지 않은 상태로 문서 편집을 저장하면, 편집 역사에 본인이 사용하는 IP(3.133.131.110) 주소 전체가 영구히 기록됩니다.

동적 프로그래밍(r30 편집)

동적 프로그래밍_{(r30 편집)}