동적 프로그래밍 : 특성, 예, 장점, 단점 - 과학 기술 - 2026

동적 프로그래밍은 복잡한 문제로 해결할 수있는 모델 알고리즘 에 의해 분할 하여 , 하위 문제에 결과를 저장하는, 그 결과를 재 계산하는 것을 방지한다.

이 일정은 유사한 하위 문제로 나눌 수있는 문제가있을 때 사용되어 결과를 다시 사용할 수 있습니다. 대부분의 경우이 일정은 최적화에 사용됩니다.

동적 프로그래밍. 피보나치 수열에 중첩 된 하위 문제. 출처 : Wikimedia commons, en : 사용자 : Dcoatzee, 추적자 : 사용자 : Stannered / Public domain

사용 가능한 하위 문제를 해결하기 전에 동적 알고리즘은 이전에 해결 된 하위 문제의 결과를 조사하려고합니다. 하위 문제에 대한 솔루션이 결합되어 최상의 솔루션을 얻습니다.

동일한 하위 문제를 반복해서 계산하는 대신이 하위 문제가 처음 발생할 때 일부 메모리에 솔루션을 저장할 수 있습니다. 다른 하위 문제를 해결하는 동안 다시 나타나면 메모리에 이미 저장된 해결 방법을 사용합니다.

이는 추가 공간을 사용하여 솔루션을 찾는 데 필요한 시간을 개선 할 수있는 메모리 시간 수정에 대한 훌륭한 아이디어입니다.

동적 프로그래밍의 특징

다음과 같은 필수 특성은 동적 프로그래밍을 적용하기 전에 문제가 있어야하는 것입니다.

최적의 하부 구조

이 특성은 최적화 문제를 구성하는 2 차 문제의 최적 솔루션을 결합하여 최적화 문제를 해결할 수 있음을 나타냅니다. 이러한 최적의 하위 구조는 재귀로 설명됩니다.

예를 들어, 그래프에서 최적의 하부 구조는 정점 s에서 정점 t로가는 최단 경로 r에 표시됩니다.

즉,이 최단 경로 r에서 중간 정점 i를 취할 수 있습니다. r이 실제로 가장 짧은 경로 인 경우 하위 경로 r1 (s에서 i로)과 r2 (i에서 t로)로 나눌 수 있습니다. 이렇게하면 해당 정점 사이의 최단 경로가됩니다.

따라서 최단 경로를 찾기 위해 솔루션을 쉽게 재귀 적으로 공식화 할 수 있습니다. 이것이 Floyd-Warshall 알고리즘이하는 일입니다.

중복되는 하위 문제

하위 문제 공간은 작아야합니다. 즉, 문제를 해결하는 모든 재귀 알고리즘은 새로운 하위 문제를 생성하는 대신 동일한 하위 문제를 반복해서 해결해야합니다.

예를 들어, 피보나치 수열을 생성하기 위해 다음과 같은 재귀 공식을 고려할 수 있습니다. Fn = F (n – 1) + F (n – 2), F1 = F2 = 1 인 기본 케이스로 가정하면 다음과 같습니다. F33 = F32 + F31 및 F32 = F31 + F30.

보시다시피 F31은 F33과 F32의 재귀 하위 트리로 확인됩니다. 하위 문제의 총 수는 매우 적지 만 이와 같은 재귀 솔루션을 채택하면 동일한 문제를 반복해서 해결하게됩니다.

이것은 동적 프로그래밍에 의해 고려되므로 각 하위 문제를 한 번만 해결합니다. 이는 두 가지 방법으로 수행 할 수 있습니다.

하향식 접근 방식

어떤 문제에 대한 해결책이 하위 문제의 솔루션을 사용하여 반복적으로 공식화 될 수 있고 이러한 하위 문제가 겹치면 하위 문제에 대한 솔루션을 쉽게 기억하거나 테이블에 저장할 수 있습니다.

새로운 하위 문제 솔루션을 검색 할 때마다 이전에 해결되었는지 확인하기 위해 표를 확인합니다. 솔루션이 저장된 경우 다시 계산하는 대신 사용됩니다. 그렇지 않으면 하위 문제가 해결되어 솔루션이 테이블에 저장됩니다.

상향식 접근 방식

문제의 해결이 하위 문제의 관점에서 반복적으로 공식화 된 후에는 문제를 오름차순으로 재구성하려는 시도를 할 수 있습니다. 먼저 하위 문제를 해결하고 해당 솔루션을 사용하여 더 큰 하위 문제에 대한 솔루션을 도출하려고합니다.

이것은 또한 일반적으로 테이블 형식으로 수행되며 더 작은 하위 문제에 대한 솔루션을 사용하여 크고 큰 하위 문제에 대한 솔루션을 반복적으로 생성합니다. 예를 들어 F31과 F30의 값을 이미 알고 있다면 F32의 값을 직접 계산할 수 있습니다.

다른 기술과의 비교

동적 프로그래밍으로 해결할 수있는 문제의 한 가지 중요한 특징은 하위 문제가 중복되어야한다는 것입니다. 이것이 가장 단순한 값을 저장할 필요가없는 분할 및 정복 기술과 동적 프로그래밍을 구별하는 것입니다.

기본 케이스를 계산할 때 최종 값을 귀납적으로 결정할 수 있기 때문에 재귀와 유사합니다. 이 상향식 접근 방식은 새 값이 이전에 계산 된 값에만 의존 할 때 잘 작동합니다.

예

1에 도달하기위한 최소 단계

양의 정수 "e"에 대해 다음 세 단계 중 하나를 수행 할 수 있습니다.

-숫자에서 1을 뺍니다. (e = e-1).

-2로 나눌 수 있으면 2로 나눕니다 (e % 2 == 0이면 e = e / 2).

-3으로 나눌 수 있으면 3으로 나눕니다 (e % 3 == 0이면 e = e / 3).

위의 단계를 기반으로 e를 1로 가져 오는 최소 단계 수를 찾아야합니다. 예 :

-e = 1이면 결과 : 0.

-e = 4이면 결과 : 2 (4/2 = 2/2 = 1).

-e = 7, 결과 : 3 (7-1 = 6/3 = 2/2 = 1).

초점

n을 가능한 한 낮게 만드는 단계를 항상 선택하고 1에 도달 할 때까지 이렇게 계속하는 것을 생각할 수 있습니다. 그러나이 전략은 여기서 작동하지 않음을 알 수 있습니다.

예를 들어, e = 10 인 경우 단계는 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 단계)입니다. 그러나 최적의 형식은 10-1 = 9/3 = 3/3 = 1 (3 단계)입니다. 따라서 발견 된 n의 각 값에 대해 수행 할 수있는 모든 단계를 시도하여 이러한 가능성의 최소 수를 선택해야합니다.

모든 것은 재귀로 시작합니다 : F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} if e> 1, 기본 케이스로 간주 : F (1) = 0. 반복 방정식이 있으면 재귀 코딩을 시작할 수 있습니다.

그러나 중복되는 하위 문제가 있음을 알 수 있습니다. 또한 주어진 입력에 대한 최적의 솔루션은 하위 문제의 최적 솔루션에 따라 다릅니다.

암기에서와 같이 해결 된 하위 문제의 솔루션은 나중에 사용하기 위해 저장됩니다. 또는 동적 프로그래밍에서와 같이 맨 아래부터 시작하여 주어진 e까지 작업합니다. 그런 다음 두 코드 :

암기

동적 상향식 프로그래밍

이점

동적 프로그래밍 사용의 주요 이점 중 하나는 이전에 계산 된 참조가 사용되기 때문에 처리 속도가 빨라진다는 것입니다. 재귀 적 프로그래밍 기술이므로 프로그램의 코드 줄을 줄입니다.

탐욕스러운 알고리즘 대 동적 프로그래밍

Greedy 알고리즘은 최적화를위한 도구라는 점에서 동적 프로그래밍과 유사합니다. 그러나 탐욕 알고리즘은 각 로컬 단계에서 최적의 솔루션을 찾습니다. 즉, 글로벌 최적을 찾기 위해 탐욕스러운 선택을 추구합니다.

따라서 욕심 많은 알고리즘은 당시에는 최적으로 보이지만 미래에는 비용이 많이 들고 글로벌 최적을 보장하지 않는 가정을 할 수 있습니다.

반면 동적 프로그래밍은 하위 문제에 대한 최적의 솔루션을 찾은 다음 이러한 하위 문제의 결과를 결합하여 정보에 입각 한 선택을 통해 실제로 가장 최적의 솔루션을 찾습니다.

단점

-저장된 값의 사용 여부를 보장 할 수없는 각 하위 문제의 계산 결과를 저장하려면 많은 메모리가 필요합니다.

-출력값은 실행 중 다음과 같은 하위 문제에 사용되지 않고 저장되는 경우가 많습니다. 이로 인해 불필요한 메모리 사용량이 발생합니다.

-동적 프로그래밍에서 함수는 재귀 적으로 호출됩니다. 이렇게하면 스택 메모리가 지속적으로 증가합니다.

재귀 vs 동적 프로그래밍

코드를 실행할 메모리가 제한되어 있고 처리 속도가 문제가되지 않는 경우 재귀를 사용할 수 있습니다. 예를 들어 모바일 애플리케이션을 개발하는 경우 애플리케이션을 실행하기 위해 메모리가 매우 제한됩니다.

프로그램을 더 빠르게 실행하고 메모리 제한이없는 경우 동적 프로그래밍을 사용하는 것이 좋습니다.

응용

동적 프로그래밍은 합당한 시간 내에 해결하기 매우 어려울 수있는 문제를 해결하는 효과적인 방법입니다.

동적 프로그래밍 패러다임을 기반으로하는 알고리즘은 계획 문제 해결에서 음성 인식에 이르기까지 인공 지능의 많은 예를 포함하여 많은 과학 분야에서 사용됩니다.

동적 프로그래밍에 기반한 알고리즘

동적 프로그래밍은 매우 효과적이며 다양한 문제에 대해 매우 잘 작동합니다. 많은 알고리즘은 다음과 같은 탐욕스러운 알고리즘 응용 프로그램으로 볼 수 있습니다.

-피보나치 수열.

-하노이의 탑.

-Floyd-Warshall을 통한 모든 짧은 경로 쌍.

-배낭 문제.

-프로젝트 일정.

-Dijkstra를 통과하는 최단 경로.

-비행 제어 및 로봇 제어.

-수학적 최적화 문제.

-시간 공유 : CPU 사용량을 최대화하기 위해 작업을 예약합니다.

피보나치 수열

피보나치 수는 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 등의 시퀀스에서 발견되는 숫자입니다.

수학적 용어에서 피보나치 수열 Fn은 반복 공식으로 정의됩니다. F (n) = F (n -1) + F (n -2), 여기서 F (0) = 0 및 F ( 1) = 1.

하향식 접근 방식

이 예에서 모든 초기 값이있는 검색 배열은 -1로 초기화됩니다. 하위 문제에 대한 솔루션이 필요할 때마다이 검색 매트릭스가 먼저 검색됩니다.

계산 된 값이 있으면 해당 값이 반환됩니다. 그렇지 않으면 나중에 재사용 할 수 있도록 결과가 검색 배열에 저장되도록 계산됩니다.

상향식 접근 방식

이 경우 동일한 피보나치 급수에 대해 f (0)이 먼저 계산 된 다음 f (1), f (2), f (3) 등이 계산됩니다. 따라서 하위 문제의 솔루션은 아래에서 위로 구성됩니다.

참고 문헌

1. Vineet Choudhary (2020). 동적 프로그래밍 소개. 개발자 내부자. 출처 : developerinsider.co.
2. Alex Allain (2020). C ++의 동적 프로그래밍. C 프로그래밍. 출처 : cprogramming.com.
3. 아카데미 이후 (2020). 동적 프로그래밍의 아이디어. 출처 : afteracademy.com.
4. Aniruddha Chaudhari (2019). 동적 프로그래밍 및 재귀-차이점, 예제의 장점. CSE 스택. 출처 : csestack.org.
5. 코드 셰프 (2020). 동적 프로그래밍을위한 자습서. 출처 : codechef.com.
6. Programiz (2020). 동적 프로그래밍. 출처 : programiz.com.