--- title: "Dynamic programming — 동적 계획법" source: "https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95" wiki: "systems-analysis.info/int" article: "Dynamic_programming_—_동적_계획법" language: "ko" categories: - "Category:Korean" - "Category:Operations research" revision_id: 1751 wiki_created_at: 2026-09-06T22:53:26Z wiki_modified_at: 2026-09-06T22:53:26Z downloaded_at: 2026-09-07T22:47:34Z --- # Dynamic programming — 동적 계획법 **동적 계획법**(**DP**; 영어: *dynamic programming, DP*)은 원래의 문제를 더 단순한 부분 문제들의 연속으로 분할하는 방식에 기반한 복잡한 최적화 문제의 풀이 방법이다^{[\[1\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-bigenc-dp-1)[\[2\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-ru-wiki-dp-2)}. 이 방법은 다단계 의사결정 과정에 적용되며, 전체 문제의 최적해를 각 부분 문제의 최적해로부터 구성할 수 있다. 이 용어는 1950년대 미국의 수학자 리처드 벨만에 의해 도입되었다^{[\[3\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-rechetnikov-dp-3)}. 이 맥락에서 '프로그래밍'이라는 단어는 컴퓨터 코드 작성이 아닌 '계획' 또는 '최적 행동 계획 수립'의 의미로 사용된다^{[\[4\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-en-wiki-dp-4)}. ## 핵심 성질과 정리 동적 계획법의 적용 가능성은 문제가 두 가지 근본적인 성질을 갖는지에 의해 결정된다. ### 벨만의 최적성 원리 이 방법의 중심 개념은 **벨만의 최적성 원리**(영어: *Bellman's principle of optimality*)이다. 이는 다음과 같이 서술된다: 초기 상태와 초기 결정이 무엇이든 간에, 이후의 결정들은 첫 번째 결정의 결과로 얻어진 상태에 대하여 최적 전략을 구성해야 한다^{[\[3\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-rechetnikov-dp-3)}. 다시 말해, 최적 경로의 어떤 부분도 그 자체로 최적이다. 이 성질은 전체 문제를 더 단순한 부분 문제들의 연속으로 분할하고 재귀적으로 풀 수 있게 해 준다. ### 중복 부분 문제 문제가 재귀적으로 풀릴 때 동일한 부분 문제가 반복적으로 나타나면, 그 문제는 **중복 부분 문제**(영어: *overlapping subproblems*) 성질을 가진다고 한다. DP는 이미 풀린 부분 문제의 해를 저장함으로써(이 기법을 메모이제이션 또는 테뷸레이션이라 한다) 중복 계산을 피할 수 있으며, 이는 단순한 재귀적 완전 탐색에 비해 효율성을 크게 향상시킨다. ## 벨만 방정식 최적성 원리로부터 이 방법의 핵심 점화식인 **벨만 방정식**^{[\[1\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-bigenc-dp-1)}이 도출된다. 이 방정식은 현재 상태의 '가치'(최적 이득 또는 비용)를 이후 상태들의 가치와 연결한다. 가산적 목적 함수를 가진 결정론적 다단계 과정에 대한 일반적인 형태는 다음과 같다: $$ V_{k - 1}(x) = \max\limits_{y \in U(x)}\{\varphi_{k}(x,y) + V_{k}(f_{k}(x,y))\} $$ 여기서: - $k$ — 단계 번호($m$에서 1까지); - $x$ — 단계 $k - 1$에서의 시스템 상태; - $y$ — 단계 $k$에서 채택되는 제어 결정; - $\varphi_{k}(x,y)$ — k번째 단계에서의 이득(또는 비용); - $f_{k}(x,y)$ — 시스템의 새로운 상태를 정의하는 함수; - $V_{k}(s)$ — 단계 $k$에서 상태 $s$로 시작하는 부분 문제에 대한 목적 함수의 최적값. 이 방정식은 일반적으로 마지막 단계에서 첫 번째 단계로 거슬러 올라가는 방식, 즉 '끝에서부터' 순차적으로 풀린다. ## 적용 예시 - **그래프에서의 최단 경로 문제**: 이 문제는 최단 경로의 어떤 구간도 그 자체로 최단이라는 최적 부분구조 성질을 가진다. 벨만-포드 알고리즘과 플로이드-워셜 알고리즘은 이 문제를 DP로 풀기 위한 고전적인 적용 사례이다^{[\[5\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-mit-amp-5)}. - **배낭 문제**: 서로 다른 가치와 무게를 가진 물건들로 제한된 용량의 배낭을 최적으로 채우는 문제이다. DP는 물건들을 순차적으로 고려하고 각 단계에서 남은 용량의 모든 가능한 값에 대해 최대 가치를 계산함으로써 이 문제를 풀 수 있다. - **자원 배분 문제**: 전체 효과를 최대화하기 위해 제한된 자원(예: 투자금)을 여러 프로젝트에 배분하는 문제이다. ## 한계 이 방법의 주요 한계는 **차원의 저주**(영어: *curse of dimensionality*)이다. 이는 시스템 상태를 기술하는 변수의 수가 증가함에 따라 상태 수가 지수적으로 증가하고 그 결과 계산 복잡도가 폭발적으로 증가하는 현상을 나타내기 위해 벨만이 도입한 용어이다^{[\[6\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-ru-wiki-curse-6)[\[7\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-utexas-ormm-7)}. 이로 인해 매우 고차원 문제에 대한 정확한 DP의 실용적 적용이 제한된다. ## 관련 개념 - 운용 과학 - 최적 제어 이론 - 마르코프 결정 과정(확률론적 일반화) - 해밀턴-야코비-벨만 방정식(연속 시간에 대한 유사체) ## 각주 ^{[\[1\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-bigenc-dp-1)} ^{[\[2\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-ru-wiki-dp-2)} ^{[\[3\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-rechetnikov-dp-3)} ^{[\[4\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-en-wiki-dp-4)} ^{[\[5\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-mit-amp-5)} ^{[\[6\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-ru-wiki-curse-6)} ^{[\[7\]](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-utexas-ormm-7)} \ 1. ↑ ^{[1.0](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-bigenc-dp_1-0)} ^{[1.1](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-bigenc-dp_1-1)} ^{[1.2](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-bigenc-dp_1-2)} "Динамическое программирование". *Большая российская энциклопедия*. [1] 2. ↑ ^{[2.0](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-ru-wiki-dp_2-0)} ^{[2.1](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-ru-wiki-dp_2-1)} "Динамическое программирование". *Википедия*. [2] 3. ↑ ^{[3.0](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-rechetnikov-dp_3-0)} ^{[3.1](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-rechetnikov-dp_3-1)} ^{[3.2](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-rechetnikov-dp_3-2)} Решетников А. Н., Коченков А. В., Пиров Д. М., Рябоконь Д. А. (2011). *Динамическое программирование. Примеры применения*. Учебное пособие, ННГУ им. Лобачевского (ВМиК). [3] 4. ↑ ^{[4.0](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-en-wiki-dp_4-0)} ^{[4.1](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-en-wiki-dp_4-1)} "Dynamic programming". *Wikipedia*. [4] 5. ↑ ^{[5.0](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-mit-amp_5-0)} ^{[5.1](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-mit-amp_5-1)} Bradley S. P., Hax A. C., Magnanti T. L. (1977). *Applied Mathematical Programming*. Addison-Wesley. [5] 6. ↑ ^{[6.0](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-ru-wiki-curse_6-0)} ^{[6.1](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-ru-wiki-curse_6-1)} "Проклятие размерности". *Википедия*. [6] 7. ↑ ^{[7.0](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-utexas-ormm_7-0)} ^{[7.1](https://systems-analysis.info/int/Dynamic_programming_%E2%80%94_%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-utexas-ormm_7-1)} Jensen P. A. (2004). *Dynamic Programming – Models*. Operations Research Models and Methods, Univ. of Texas. [7]