동적 계획법

DP(Dynamic programming)란 컴퓨터 과학에서, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 동적 계획법이라고도 한다.

개요

DP의 원리는 일반적으로 주어진 문제를 풀기 위해서 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 DP는 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. DP 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 왜냐하면 DP는 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문이다. 이에 우리는 DP를 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법이라고 생각할 수 있다. 그러나 문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우, DP는 최적의 해법이라고 말할 수 있다. 때로는 단순한 재귀함수에 저장 수열(이전의 데이터를 모두 입력하는 수열)을 대입하는 것 만으로도 최적해를 구할 수 있는 동적 알고리즘을 찾을 수 있다. 그러나 대다수의 문제는 이보다 훨씬 더 복잡한 프로그래밍을 요구한다. 그 중에 일부는 여러 개의 매개 변수를 이용하여 재귀 함수를 작성해야 하는 것도 있고, 아예 이러한 방법으로 동적 알고리즘을 짤 수 없는 문제 또한 존재한다. 이러한 퍼즐로는 대표적으로 에그 드로핑 퍼즐(Egg Dropping Puzzle)이 있다.

역사

DP라는 용어는 리처드 벨먼(Richard Bellman)이 1940년대에 최고의 결정을 차례로 찾아야 하는 문제를 해결하는 과정을 설명하기 위해 사용했던 용어이다. 1953년까지 그는 특히 더 큰 의사결정에 더 작은 의사결정 문제를 내포하는 것을 언급하면서 이를 현대적 의미로 다듬었고, 이후 이 분야는 전기전자기술자협회(IEEE)에 의해 시스템 분석 및 엔지니어링 주제로 인식되었다. 벨먼의 기여는 반복적인 형태로 최적화 문제를 재현하는 DP의 중심 결과인 벨먼 방정식의 이름으로 기억된다. 벨만은 그의 자서전, '태풍의 눈'(Eye of the Hurricane)에서 다음과 같이 말했다.

 나는 랜드(RAND) 코퍼레이션에서 1950년의 가을을 보냈다.
 여기에서 내게 주어진 첫 과제는 다단계(multistage) 의사 결정 프로세스에 대해 적절한 용어를 명명하는 것이었다.
 'DP'라는 이름이 어디에서 왔는지 궁금하지 않은가?
 1950년대는 내가 수학에 대해 연구하기에는 좋지 못한 시기였다.
 우리는 그 때 워싱턴에서 윌슨이라는 사람과 함께 일하고 있었다.
 윌슨은 연구라는 것에 대해 굉장히 병적인 공포를 가지고 있었다.
 사람들이 그 앞에서 연구에 대해 이야기를 꺼내면 그는 완전히 미치다시피 했다.
 그러나 불행히도 랜드는 공군 소속의 회사였고, 윌슨은 그 공군의 간부인 국방 위원장이었다.
 그래서 내가 랜드 안에 있었을 때 윌슨을 비롯한 공군들이 내가 수학에 대해 연구하는 것을 보이지 않게 막는다는 것을 알 수 있었다.
 처음 올 때는 나는 위의 문제에 대해 '의사 결정 프로세스'라는 이름을 사용했지만,
 여기에서 '프로세스(Process)'라는 단어를 사용하는데 여러가지 차질이 생겨버리고 만 것이다.
 그래서 나는 사람들이 알지 못하게 '계획법(Programming)'이라는 단어를 붙였다.
 또한 나는 이 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, '동적(Dynamic)'이다라는 개념(idea)이 전달되길 원했다.
 이 단어야말로 내가 연구하는 알고리즘의 성질을 정확하게 짚어내었고,
 게다가 윌슨에게도 피해를 입히지 않으며 공군도 이 단어에선 꼬투리를 잡지 못했으니 그야말로 일석이조의 효과를 누린 것이다.

즉, 'Dynamic'이라는 말은 벨먼이 이런 알고리즘의 '시가변적이며 다단계적인' 특성을 나타내기 위해서 채택한 용어인 것이다. 또한 'Programming'이라는 단어는 공군 내에서도 워드 프로세스 교육이나 군수 물자 운송 등에 이용되는 단어였기 때문에 사용하는데 아무 제약이 없었던 것이다. 이렇게 만들어진 'DP'라는 단어는 선형 계획법이나 수리 계획법처럼 하나의 프로그래밍 기법을 나타내는 단어가 되었다.

이론

DP가 적용되기 위해서 문제가 가져야 하는 두 가지 핵심 속성이 있는데, 바로 최적의 하부 구조와 중복되는 하위 문제이다. 오버랩되지 않는 서브 문제에 최적의 솔루션을 결합해 문제를 해결할 수 있다면 그 전략을 대신 '분할과 정복'이라고 한다. 병합 분류와 빠른 분류가 동적 프로그래밍 문제로 분류되지 않는 이유이다. 최적 하위 구조란 주어진 최적화 문제에 대한 해결책을 하위 문제에 대한 최적 해결책의 조합에 의해 얻을 수 있다는 것을 의미한다. 그러한 최적의 하부 구조는 대개 재귀의 수단으로 설명된다. 예를 들어, 그래프 G=(V,E)를 보면, 꼭지점 u에서 꼭지점 v까지의 최단 경로 p는 최적의 하부 구조를 나타낸다. 즉, 이 최단 경로 p에서 중간 정점 w를 취한다. p가 정말로 최단 경로인 경우, 이는 실제로 해당 정점 사이의 최단 경로(알고리즘 소개에서 설명한 단순 절단 및 붙여넣기 인수에 의해)가 되도록 u에서 w까지, p2로 하위 경로 p1로 분할될 수 있다. 따라서 벨만-포드(Bellman–Ford) 알고리즘이나 플로이드-워셸(Floyd–Warshall) 알고리즘이 하는 재귀적인 방법으로 최단 경로를 찾기 위한 솔루션을 쉽게 공식화할 수 있다. 하위 문제가 중복되는 것은 하위 문제의 공간이 작아야 한다는 것을 의미하며, 즉 문제를 해결하는 모든 재귀 알고리즘은 새로운 하위 문제를 생성하는 것이 아니라 동일한 하위 문제를 반복해서 해결해야 한다. 예를 들어, 피보나치(Fibonacci) 영상 시리즈 생성을 위한 재귀적 공식은 다음과 같다. Fi = Fi-1 + Fi-2, 베이스 케이스 F1 = F2 = 1. 그 다음 F43 = F42 + F41, 그리고 F42 = F41 + F40. 현재 F41은 F42뿐만 아니라 F43의 재귀 하위 트리에서 해결되고 있다. 하위문제의 총수가 실제로 작더라도(그 중 43개만) 이와 같은 순진한 재귀적 해결책을 채택하면 결국 같은 문제를 반복해서 해결하게 된다. DP는 이 사실을 감안하여 각각의 하위 문제를 단 한 번만 해결한다. 이에 대한 접근 방식은 다음과 같다.

• 하향식 접근 방식: 이것은 어떤 문제의 재귀적 공식화에서 직접적인 탈락이다. 만약 어떤 문제에 대한 해결책을 그것의 하위 문제에 대한 해결책을 사용하여 반복적으로 공식화할 수 있고, 그것의 하위 문제가 중복된다면, 그 해결책을 쉽게 메모하거나 표에 하위 문제에 대한 해결책을 저장할 수 있다. 새로운 하위 문제를 해결하려고 할 때마다 먼저 테이블에서 이미 해결이 되었는지 확인한다. 해결책이 기록된 경우에는 직접 사용할 수 있고, 그렇지 않으면 하위 문제를 해결하고 그 해결책을 표에 추가한다.
• 상향식 접근법: 일단 하위 문제처럼 반복적으로 문제에 대한 해결책을 공식화하면, 우리는 하위 문제를 먼저 해결하고 그들의 해결책을 빌드온(built-on)하여 더 큰 하위 문제에 대한 해결책에 도달하는 바텀업 방식으로 문제를 개혁해 볼 수 있다. 이것은 또한 작은 하위 문제에 대한 해결책을 사용하여 더 크고 더 큰 하위 문제에 대한 해결책을 반복적으로 생성함으로써 표 형식으로 이루어진다. 예를 들어 F41과 F40의 값을 이미 알고 있다면 F42의 값을 직접 계산할 수 있다.

참고자료

• 동적 계획법 위키백과 - https://ko.wikipedia.org/w/index.php?title=%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95&action=edit&section=3
• Dynamic programming Wikipedia - https://en.wikipedia.org/wiki/Dynamic_programming#History

같이 보기

• 강화학습

이 동적 계획법 문서는 인공지능 기술에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

인공지능 : 인공지능 서비스, 인공지능 로봇, 인공지능 기술 □■⊕, 인공지능 기업, 인공지능 인물 인공지능 기술 AI 워싱 • 로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지능 • 지식표현 • 컴퓨터 비전 • 튜링 테스트 • 프롬프트 • 프롬프트 엔지니어링 문자인식과 음성인식 ICR • OCR • OMR • TTS • 답변 • 대화 • 문자 • 문자인식 • 스토리 • 음성 • 음성인식(STT) • 인공어 • 자연어 • 질문 • 화자인식 인공지능 데이터 데이터라벨러 • 데이터라벨링 • 데이터셋 • 크라우드워커 • 토큰 • 토큰화 인공지능 학습 ADP • CoLLM • DALL-E • DDPG • DQN • LMM • SARSA • SLM • 강화학습 • 거대언어모델(LLM) • 결정이론적 메타추론 • 계통적 강화학습 • 동적 계획법 • 딥러닝 • 딥큐러닝 • 머신러닝(기계학습) • 모델 기반 강화학습 • 모델 프리 강화학습 • 미세조정 • 반영식 아키텍처 • 비지도학습 • 사전학습 • 수시 알고리즘 • 심층믿음망 • 어니 • 에이전트 • 인공지능 학습 • 지도학습 • 학습 • 확률적 경사하강법 인공지능 알고리즘 AGI • ANI • ASI • RAG • XAI • 관계형 네트워크(RN) • 다층퍼셉트론 • 데이터마이닝 • 방사신경망 • 분산 샌드박스 • 생성대립신경망(GAN) • 생성형 AI • 수퍼얼라인먼트 • 순전파 • 순환신경망(RNN) • 시그모이드 함수 • 신경망 구조 • 심층신경망(DNN) • 심층신뢰신경망(DBN) • 양방향 비고정값 암호 체계(TSID) • 역전파 • 인공신경망(ANN) • 인공지능(AI) • 제한 볼츠만 머신(RBM) • 전방전달신경망 • 코헨 자기조직 신경망 • 텍스트마이닝 • 트랜스포머 • 파이 • 퍼셉트론 • 합성곱 신경망(CNN) 계산복잡도 NP • NP-완전 • 계산복잡도 • 공간복잡도 • 시간복잡도 • 여 NP • 여 NP-완전 인공지능 프로그램 BCI • GPT • 딥블루 • 딥페이크 • 멀티모달 AI • 모달 • 모달리티 • 모달창 • 알렉스넷 • 어니 • 알파고 • 알파고제로 • 알파폴드 • 왓슨 • 카페 • 컨트롤넷 • 텐서플로 • 텔레파시 • 토치 • 파이토치 • 한돌 인공지능 특징 결정이론 • 계산상의 합리성 • 논리학 • 논리주의자 • 분산성 • 불확실성 • 삼단논법 • 선호도 • 예측곤란성 • 완벽한 합리성 • 유계 합리성 • 이유 불충분의 원리 • 자율성 • 최대기대효용 • 할루시네이션 • 효용이론 인공지능 법적 지위 권리주체성 • 소버린 AI • 전자대리인 • 전자적 인간 • 책임법 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반