동적 프로그래밍 소개: 겹치는 부분 문제와 최적의 부분 구조

게시 됨: 2021-02-08

목차

소개

25의 제곱을 푸는 문제가 있다고 가정해 보겠습니다. 이 문제에 처음 직면하는 경우 손에 넣거나 계산기를 사용하여 해결할 수 있습니다. 하지만 이 문제를 본 적이 있거나 해결한 적이 있다면 외워서 빠르게 답할 가능성이 있습니다.

이것은 우리가 그것을 기억할 수 있다면 다음에 그것을 건너뛸 수 있다는 결론에 이르게 합니다. 동적 프로그래밍은 유사한 개념에서 작동하며, 아이디어는 계산 결과를 기억하고 필요한 경우 나중에 사용하는 것입니다.

이 간단한 동적 프로그래밍 절차는 프로그래머가 효율적인 코드와의 전쟁에서 승리할 수 있는 강력한 무기가 됩니다.

예를 들어 복잡한 질문이 있고 항상 질문을 하위 문제로 나누는 솔루션을 생각한다고 가정해 보겠습니다. 그러나 하위 문제를 여러 번 계산해야 하는 상황에 봉착할 수 있습니다. 거기에서 최적의 솔루션을 위해 동적 프로그래밍을 사용합니다.

동적 프로그래밍에는 두 가지 개념이 있습니다.

  1. 겹치는 하위 문제
  2. 최적의 하부구조

겹치는 하위 문제

중첩 하위 문제 개념을 이해하는 고전적인 예는 피보나치 수열을 인쇄하는 프로그램입니다.

피보나치 수열의 논리는 "피보나치(n) = 피보나치(n-1) + 피보나치(n-2)"로 표시됩니다. 그리고 fibonacci(0)=0 및 fibonacci(1)=1의 기본 경우를 사용하여 이 함수를 원활하게 실행하는 것은 재귀 솔루션을 사용하여 수행할 수 있습니다.

공개 정적 정수 피보나치(int n){
 if (n== 0 || n== 1 )
 리턴 n;
 피보나치(n -1 )+피보나치(n -2 )를 반환 합니다.
 }
 공개 정적 무효 메인(문자열[] 인수){
 System.out.print( "4번째 피보나치 수는 " +fibonacci( 4 ) );
 }

4번째 피보나치 숫자를 출력해야 한다고 가정하면 재귀 트리는 다음과 같이 됩니다.

피보나치(4)

/ \

피보나치(3) + 피보나치(2)

/ \ / \

피보나치(2) + 피보나치(1) 피보나치(1) + 피보나치(0)

/ \

피보나치(1) + 피보나치(0)

fibonacci(4)는 fibonacci(0)에서 시작하기 때문에 fibonacci 수열의 5번째 숫자입니다. 위의 재귀 트리에서 fibonacci(2)가 두 번 반복되는 것을 볼 수 있습니다. 우리는 높이가 4인 재귀 트리에서 중복을 관찰했습니다. 이제 엄청난 수의 재귀 호출이 있다고 상상해 보십시오. 그 후 높이가 큰 재귀 트리가 있을 것입니다. 그리고 중복된 하위 문제로 알려진 중복 계산이 많이 있을 것입니다.

이 (i)표 작성, (ii) 메모화를 처리하는 두 가지 방법이 있습니다.

구현 과정을 살펴봄으로써 이해하도록 합시다.

메모이제이션

메모이제이션 방법을 사용하여 피보나치 문제를 해결하는 방법은 다음과 같습니다.

정적 int[] 메모;
공개 정적 정수 피보나치(int n){
if(메모[n]!=-1)
회신 메모[n];
if(n==0 || n==1){
메모[n]=n;
리턴 n;
}
메모[n] = 피보나치(n-1)+피보나치(n-2);
회신 메모[n];
}
공개 정적 무효 메인(문자열[] 인수){
메모=새로운 정수[5];
for(int i=0;i<=4;i++)
메모[i]=-1;
System.out.println("4번째 피보나치 수는 "+피보나치(4));
}

위의 코드에서는 로그 파일을 유지 관리하거나 룩업 테이블을 유지 관리하고 계산 결과 값을 저장하고 있습니다. 계산된 값을 모두 기억했으므로 필요한 경우 나중에 사용할 수 있으므로 중복 계산 및 중복 하위 문제를 피할 수 있습니다.

모든 논리는 재귀 솔루션과 유사하지만 우리가 만든 유일한 차이점은 값을 기본 메서드로 반환하기 전에 메모 배열에 기록했다는 것입니다. 이 알고리즘에 대한 유일한 제약은 크기가 O(n)인 추가 공간이 필요하지만 이전 재귀 솔루션을 최적화한다는 것입니다.

표

이 방법은 위의 솔루션과 약간 다릅니다. 메모이제이션은 동일한 재귀 솔루션을 따릅니다. 그러나 표에서는 반복 솔루션을 따릅니다. 상향식 접근이라고도 합니다. 상향식 접근 방식의 구현을 살펴보겠습니다.

공개 정적 정수 피보나치(int n){
 정수 테이블[]=새로운 정수[n+ 1 ];
 ( int i= 0 ;i<=n;i++){
 if (i== 0 || i== 1 )
 테이블[i]=i;
 다른 {
 테이블[i]=테이블[i -1 ]+테이블[i - 2 ];
 }
 }
 반환 테이블[n];
 }
 공개 정적 무효 메인(문자열[] 인수){
 System.out.println( "4번째 피보나치 수는 " +피보나치( 4 ));
 }

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)라는 것을 알고 있듯이, 메모이제이션에서 우리는 fibonacci(4) 함수 호출로 시작했고, 그 다음 우리는 그 값을 계산하지 않았다는 것을 깨달았습니다. 그래서 우리는 값을 계산한 다음 저장했습니다.

fibonacci(3), fibonacci(2)와 같은 추가 재귀 호출에서도 비슷한 상황이 발생합니다. 이제 많은 재귀 호출이 재귀 스택에서 대기하지만 어쨌든 중복되는 하위 문제의 중복을 건너뜁니다.

또한 0에서 n번째 요소까지 반복적으로 피보나치를 계산한 다음 n번째 피보나치 요소를 반환하는 방법이 있습니다. 이것이 우리가 위의 코드에서 구현한 것입니다. 이 코드도 동일한 공간 요구 사항 O(n)을 갖습니다.

확인: 풀 스택 개발자가 되기 위한 기술

최적의 하부구조

이 개념에서는 해당 하위 문제를 최적으로 해결한 경우에만 문제에 대한 최적의 솔루션을 얻을 수 있습니다.

그리고 이 개념의 전형적인 예는 그래프의 노드 간 순회를 고려하는 것입니다.

Telangana에서 Delhi까지 여러 루트가 있다고 가정해 보겠습니다. 그리고 Nagpur와 Gwalior를 통과하는 최단 경로가 있다면. 그런 다음 나그푸르에서 델리까지의 최단 경로는 괄리오르를 거쳐야 합니다. 이제 우리는 문제를 Telangana에서 Nagpur로, Nagpur에서 Gwalior로, Gwalior에서 Delhi로 하위 문제로 나눌 수 있습니다.

그리고 이 속성에 대한 고전적인 예는 두 문자열에서 가장 긴 공통 하위 시퀀스입니다. 하위 시퀀스는 하위 문자열과 다릅니다. 하위 시퀀스에서 문자는 원래 문자열의 결과일 필요가 없습니다.

따라서 아이디어는 하위 문제를 최적으로 해결하여 해결하는 것입니다. n을 가장 긴 공통 부분 수열의 길이라고 하자.

n=LCS(감자, 문신)이면 n=LCS(감자, 문신)+1(마지막 문자가 같은 경우), 그렇지 않으면 n=최대(LCS(감자, 문신), LCS(감자, 문신)입니다.

정적 int lcs(문자열 s1, 문자열 s2, int m, int n ){
 int dp[][] = 새로운 int[m+ 1 ][n+ 1 ];
 ( int i= 0 ; i<=m; i++){
 ( int j= 0 ; j<=n; j++){
 if (i == 0 || j == 0 )
 dp[i][j] = 0 ;
 그렇지 않으면 (s1.charAt(i -1 ) == s2.charAt(j -1 ))
 dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
 또 다른
 dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
 }
 }
 반환 dp[m][n];
 }
 공개 정적 무효 메인(문자열[] 인수){
 System.out.println( "가장 긴 공통 부분 수열의 길이는 " +lcs( "potato" , "tattoo" , 6 , 6 ));
 }

위의 코드에서 우리는 표 방식을 사용하여 로직을 구현했고 두 문자열에 존재하는 가장 긴 공통 부분 시퀀스의 길이를 계산했습니다.

또한 읽기: 인도의 전체 스택 개발자 급여

세계 최고의 대학에서 온라인으로 소프트웨어 개발 과정을 배우십시오 . 이그 제 큐 티브 PG 프로그램, 고급 인증 프로그램 또는 석사 프로그램을 획득하여 경력을 빠르게 추적하십시오.

결론

효율적인 코드와의 전쟁을 정복하기 위해 강력한 기술 중 하나를 사용하는 방법을 알고 있으므로 다른 문제에 대해 동적 프로그래밍을 구현하고 동적 프로그래밍을 사용하여 질문을 코딩하는 능력을 강화해 보십시오.

결론적으로 풀스택 개발자 과정은 웹 개발과 관련된 모든 것을 다룰 수 있는 고도로 숙련된 전문가입니다. 이러한 풀 스택 개발자 기술은 프론트엔드 및 백엔드 개발자와 구별되는 것입니다.

동적 프로그래밍이란 무엇입니까?

컴퓨터 프로그램에는 반복적인 코드가 많이 포함되어 있습니다. 이는 비효율적이며 성능에 영향을 줄 수 있습니다. 이 경우 동적 프로그래밍이 사용됩니다. 동적 프로그래밍은 복잡한 문제를 더 간단한 하위 문제로 나누고 각 하위 문제를 한 번만 풀고 해당 솔루션을 테이블을 사용하여 저장하고 나중에 유사한 하위 문제가 발생할 때마다 조회하여 해결하는 방법입니다. 복잡한 문제의 해결책. 동적 프로그래밍 알고리즘은 운영 연구, 통계 추정, 패턴 인식, 인공 지능, 기계 학습, 전산 생물학 및 기타 분야에서 다양한 유형의 최적화 문제를 해결하는 데 사용됩니다.

동적 프로그래밍에서 중첩 하위 문제는 무엇입니까?

중첩 하위 문제는 하위 문제에 다른 하위 문제에서도 사용되는 솔루션이 있을 때 사용되는 개념입니다. 이 중복으로 인해 동일한 하위 작업이 두 번 이상 해결됩니다. 문제는 하위 작업을 한 번만 해결하는 방법을 찾고 그 솔루션을 사용하여 다른 하위 문제의 솔루션을 얻는 것입니다. 동적 프로그래밍 알고리즘은 메모이제이션을 사용하여 이 문제를 해결합니다. 메모이제이션은 하위 문제에 대한 솔루션을 저장하여 다시 해결할 필요가 없도록 하는 기술입니다.

동적 프로그래밍에서 최적의 하부구조는 무엇인가?

최적 하위 구조는 문제에 대한 최적의 솔루션이 동일한 문제 정의 내에서 더 작은 문제에 대한 최적의 솔루션과 관련되어 있음을 의미합니다. 최적 하부 구조는 문제를 해결하거나 솔루션이 없음을 증명하는 데 필요한 추가 요구 사항입니다. 최적의 하위 구조를 사용하면 많은 문제를 NP-hard로 증명할 수 있습니다. DP 문제를 해결하기 위한 일반적인 접근 방식은 동적 계획법 행렬을 사용하여 하위 문제의 최적 솔루션을 저장하는 것입니다. 동적 계획법 행렬은 0이 아닌 최적 하위 구조 DP 문제를 해결하는 데 사용할 수 있습니다.