동적 프로그래밍은 수학자이자 경제학자인 Richard Bellman이 개발한 개념입니다.
당시 Bellman은 복잡한 최적화 문제를 해결할 방법을 찾고 있었습니다. 최적화 문제는 일련의 옵션에서 최상의 솔루션을 선택해야 합니다.
최적화 문제의 예는 여행하는 외판원 문제입니다. 목표는 세일즈맨이 각 도시를 정확히 한 번 방문하고 시작 도시로 돌아갈 수 있는 최단 경로를 찾는 것입니다.
이러한 문제에 대한 Bellman의 접근 방식은 문제를 더 작은 하위 문제로 나누고 가장 작은 문제부터 가장 큰 문제까지 하위 문제를 해결하는 것이었습니다. 그런 다음 하위 문제의 결과를 저장하고 더 큰 하위 문제를 해결하는 데 재사용했습니다. 이것이 동적 프로그래밍의 기본 아이디어입니다.
목차
동적 프로그래밍이란 무엇입니까?
동적 프로그래밍은 최적화 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 한 번 해결하고, 더 큰 문제를 해결하기 위해 재사용하고 결합할 수 있도록 솔루션을 저장하여 해결합니다. 문제는 가장 작은 것부터 가장 큰 것까지 해결되어 솔루션을 재사용할 수 있습니다.
동적 프로그래밍은 어떻게 작동합니까?
동적 프로그래밍을 사용하여 문제를 해결하려면 다음 단계가 필요합니다.
이를 실제로 확인하기 위해 이 프로세스를 사용하여 6번째 피보나치 수인 F(6)을 계산합니다.
먼저 해결해야 할 하위 문제를 정의합니다.
F(n) = n > 1인 경우 F(n-1) + F(n-2)
따라서: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
에프(1) = 1
F(0) = 0
두 번째 단계는 재귀 함수 또는 반복 프로세스를 사용하여 각 하위 문제를 해결하는 것입니다. 우리는 더 작은 하위 문제의 결과를 재사용하여 가장 작은 문제부터 가장 큰 문제까지 하위 문제를 해결합니다. 이것은 우리에게 다음을 제공합니다:
F(0) = 0
에프(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
각 하위 문제를 해결할 때 솔루션을 배열이나 테이블에 저장하여 다음과 같이 더 큰 하위 문제를 해결하는 데 재사용할 수 있습니다.
모든 하위 문제가 해결되면 솔루션을 사용하여 원래 문제에 대한 솔루션을 구성합니다.
이 경우 원래 문제의 해는 가장 큰 문제에서 식별된 하위 문제인 F(5)와 F(4)의 결과를 합산하여 구하는 6번째 피보나치 수입니다. 결과는 8입니다.
동적 프로그래밍이 사용되는 위치와 이유는 무엇입니까?
동적 프로그래밍은 더 작은 하위 문제로 나눌 수 있는 문제가 있는 영역에서 사용되며 해당 솔루션은 더 큰 문제를 해결하는 데 사용됩니다.
이러한 영역에는 컴퓨터 과학, 경제학, 수학 및 공학이 포함됩니다. 컴퓨터 과학에서는 시퀀스, 그래프 및 정수 값과 관련된 문제를 해결하고 경쟁 프로그래밍에 사용됩니다.
경제학에서는 재무, 생산 및 자원 할당의 최적화 문제를 해결하는 데 사용됩니다. 수학에서 동적 프로그래밍은 최적화 문제를 해결하는 데 사용되는 게임 이론, 통계 및 확률에 사용됩니다.
공학에서는 자원 할당, 스케줄링, 제조, 통신 및 제어 시스템의 문제를 해결하는 데 사용됩니다.
동적 프로그래밍을 사용하여 최적화 문제를 해결하면 몇 가지 이점이 있습니다.
최적화 문제를 해결할 때 동적 프로그래밍은 솔루션의 효율성을 보장하는 매우 유용한 도구입니다.
동적 프로그래밍에 사용되는 접근 방식
동적 프로그래밍에서는 최적화 문제를 해결하기 위해 두 가지 접근 방식이 사용됩니다. 하향식 접근 방식과 상향식 접근 방식이 있습니다.
하향식 접근법
이 접근 방식은 메모이제이션이라고도 합니다. 메모이제이션은 함수 호출 결과를 캐시에 저장하고 캐시된 결과를 다음에 다시 계산하는 대신 필요할 때 반환함으로써 컴퓨터 프로그램을 더 빠르게 만드는 데 주로 사용되는 최적화 기술입니다.
하향식 접근 방식에는 재귀 및 캐싱이 포함됩니다. 재귀는 문제의 더 간단한 버전을 인수로 사용하여 자신을 호출하는 함수를 포함합니다. 재귀는 문제를 더 작은 하위 문제로 분해하고 하위 문제를 해결하는 데 사용됩니다.
하위 문제가 해결되면 그 결과가 캐시되어 유사한 문제가 발생할 때마다 재사용됩니다. 하향식은 이해하고 구현하기 쉽고 하위 문제를 한 번만 해결합니다. 그러나 단점은 재귀 때문에 많은 메모리를 차지한다는 것입니다. 이로 인해 스택 오버플로 오류가 발생할 수 있습니다.
상향식 접근 방식
표 작성이라고도 하는 상향식 접근 방식은 재귀를 사용하지 않고 반복으로 대체하여 스택 오버플로 오류를 방지합니다.
이 접근 방식에서는 큰 문제를 더 작은 하위 문제로 나누고 하위 문제에 대한 솔루션을 사용하여 더 큰 문제를 해결합니다.
더 작은 하위 문제는 먼저 가장 큰 문제부터 가장 작은 문제로 해결되고 그 결과는 행렬, 배열 또는 테이블에 저장되므로 이름이 표입니다.
저장된 결과는 하위 문제에 의존하는 더 큰 문제를 해결합니다. 그런 다음 이전에 계산된 값을 사용하여 가장 큰 하위 문제를 해결하여 원래 문제의 결과를 찾습니다.
이 접근 방식은 재귀를 사용하지 않음으로써 메모리와 시간을 효율적으로 사용할 수 있다는 장점이 있습니다.
동적 프로그래밍으로 해결할 수 있는 문제의 예
다음은 동적 프로그래밍을 사용하여 해결할 수 있는 몇 가지 프로그래밍 문제입니다.
#1. 배낭 문제
출처: 위키백과
배낭은 캔버스, 나일론 또는 가죽으로 만든 가방으로 일반적으로 뒷면에 끈을 매고 군인과 등산객이 보급품을 운반하는 데 사용합니다.
배낭 문제에서는 배낭이 제시되고 배낭의 용량이 주어지면 각각의 가치가 있는 항목을 선택해야 합니다. 선택한 항목의 최대 총 가치를 얻고 항목의 무게가 배낭 용량보다 작거나 같도록 선택해야 합니다.
배낭 문제의 예는 다음과 같습니다.
하이킹 여행을 가고 있고 15kg 용량의 배낭이 있다고 상상해보십시오. 아래 표와 같이 가치 및 무게와 함께 가져올 수 있는 항목 목록이 있습니다.
항목값무게텐트2003침낭1502스토브501음식1002물병100.5구급상자251
총 무게가 배낭 용량인 15kg보다 작거나 같으면서 항목의 총 가치가 최대가 되도록 가져올 항목의 하위 집합을 선택합니다.
배낭 문제의 실제 적용에는 위험을 최소화하고 이익을 극대화하기 위해 포트폴리오에 추가할 증권을 선택하고 원자재를 줄이는 가장 낭비가 적은 방법을 찾는 것이 포함됩니다.
#2. 일정 문제
스케줄링 문제는 작업을 리소스 집합에 최적으로 할당하는 것이 목표인 최적화 문제입니다. 리소스는 작업을 완료하는 데 사용되는 기계, 인력 또는 기타 리소스일 수 있습니다.
일정 문제의 예는 다음과 같습니다.
직원 팀이 완료해야 하는 일련의 작업 일정을 계획하는 프로젝트 관리자라고 상상해 보십시오. 각 작업에는 시작 시간, 종료 시간 및 완료할 자격이 있는 직원 목록이 있습니다.
다음은 작업 및 해당 특성을 설명하는 표입니다.
작업시작 시간종료 시간자격을 갖춘 직원T1911A, B, CT21012A, CT31113B, CT41214A, B
각 작업을 직원에게 할당하여 총 완료 시간을 최소화합니다.
기계, 재료, 도구 및 노동과 같은 자원 할당을 최적화하려고 할 때 제조 산업에서 스케줄링 문제에 직면할 수 있습니다.
병상, 인력 및 의료 용품의 사용을 최적화할 때 의료 분야에서도 발생할 수 있습니다. 이 문제가 발생할 수 있는 다른 산업은 프로젝트 관리, 공급망 관리 및 교육입니다.
#삼. 여행하는 세일즈맨 문제
출처: 위키백과
이것은 동적 프로그래밍을 사용하여 해결할 수 있는 가장 많이 연구된 최적화 문제 중 하나입니다.
순회 외판원 문제는 도시 목록과 각 도시 쌍 사이의 거리를 제공합니다. 각 도시를 정확히 한 번 방문하고 출발 도시로 돌아가는 최단 경로를 찾아야 합니다.
여행하는 세일즈맨 문제의 예는 다음과 같습니다.
당신이 최단 시간 내에 일련의 도시를 방문해야 하는 영업 사원이라고 상상해 보십시오. 아래 표와 같이 방문해야 하는 도시 목록과 각 도시 쌍 사이의 거리가 있습니다.
도시ABCDEA010152030B100352515C153503020D202530010E301520100
여행하는 세일즈맨 문제는 관광객을 위한 경로를 계획할 때 레저 산업, 상품 운송을 계획할 때 물류, 버스 노선을 계획할 때 운송, 판매 산업 등에서 발생할 수 있습니다.
분명히 동적 프로그래밍에는 많은 실제 응용 프로그램이 있으며 이에 대해 자세히 알아볼 수 있습니다.
동적 프로그래밍에 대한 지식을 설명하려면 다음 리소스를 고려하십시오.
자원
Richard Bellman의 동적 프로그래밍
동적 프로그래밍은 동적 프로그래밍을 고안하고 초기 단계에서 개발한 Richard Bellman의 저서입니다.
이 책은 수학과 미적분학에 대한 기본적인 지식만 있으면 글을 이해할 수 있을 정도로 이해하기 쉽게 쓰여졌다. 책에서 Bellman은 동적 프로그래밍의 핵심인 다단계 결정 프로세스의 수학적 이론을 소개합니다.
그런 다음 이 책은 다단계 생산 프로세스의 병목 현상 문제, 존재 및 고유성 정리, 최적 재고 방정식을 조사합니다.
이 책의 가장 좋은 점은 Bellman이 물류, 스케줄링 이론, 통신 이론, 수리 경제학 및 제어 프로세스와 같은 분야의 많은 복잡한 문제의 예를 제공하고 동적 프로그래밍이 문제를 해결하는 방법을 보여 준다는 것입니다.
이 책은 Kindle, 양장본 및 페이퍼백 버전으로 제공됩니다.
동적 프로그래밍 알고리즘 마스터 코스
Udemy의 이 동적 프로그래밍 알고리즘 마스터 과정은 Google의 소프트웨어 엔지니어인 Apaar Kamal과 Google과 함께 일한 Prateek Narang이 제공합니다.
이 과정은 학습자가 동적 프로그래밍이 필요한 많은 문제를 다루는 프로그래밍 경쟁에서 뛰어난 성과를 낼 수 있도록 최적화되어 있습니다.
프로그래밍 경쟁자 외에도 이 과정은 알고리즘에 대한 이해를 향상시키려는 프로그래머와 프로그래밍 인터뷰 및 온라인 코딩 라운드를 준비하는 사람들에게 이상적입니다.
40시간이 넘는 이 과정은 동적 프로그래밍을 심층적으로 다룹니다. 이 과정은 먼저 재귀 및 역추적과 같은 개념에 대한 재교육을 제공합니다.
그런 다음 게임 이론, 문자열, 트리 및 그래프, 행렬 지수화, 비트 마스크, 조합론 및 하위 시퀀스, 분할 문제, 다차원 동적 프로그래밍 등의 동적 프로그래밍을 다룹니다.
경쟁력 있는 프로그래밍 필수 요소, 마스터 알고리즘
Udemy는 Prateek Narang 및 Amal Kamaar의 경쟁 프로그래밍 필수 과정을 제공합니다. 이 과정은 경쟁 프로그래머에게 유용하고 관련된 방식으로 동적 프로그래밍, 수학, 정수 이론, 고급 데이터 구조 및 알고리즘을 다룹니다.
이 과정은 경쟁 프로그래밍에 유용한 더 복잡한 알고리즘과 기술에 들어가기 전에 데이터 구조와 알고리즘에 대한 재교육을 제공합니다.
이 과정은 동적 프로그래밍, 수학, 게임 이론, 패턴 매칭, 비트마스킹 및 프로그래밍 대회에서 사용 및 테스트된 수많은 고급 알고리즘을 다룹니다.
Udemy 과정은 10개의 모듈과 42개의 섹션으로 나뉘며 각 섹션 후에 많은 연습 문제를 제공합니다. 이 베스트 셀러 과정은 경쟁 프로그래밍에 관심이 있는 모든 사람에게 필수 코스입니다.
마지막 말
동적 프로그래밍은 모든 프로그래머가 실제 문제에 대한 문제 해결을 개선하는 방법을 배우는 데 유용한 기술입니다. 따라서 프로그래머는 제안된 리소스를 검토하여 이 중요한 도구를 도구 상자에 추가하는 것을 고려해야 합니다.
다음으로 데이터 과학에 사용할 프로그래밍 언어를 확인할 수 있습니다.