동적 프로그래밍은 문제를 하위 문제로 나누고 나중에 결과를 다시 계산할 필요가 없도록 결과를 저장하는 기술입니다. 전체 솔루션을 최적화하기 위해 하위 문제를 최적화하는 것을 최적 하위 구조 속성이라고 합니다. 동적 프로그래밍의 주요 용도는 최적화 문제를 해결하는 것입니다. 여기서 최적화 문제는 문제의 최소 또는 최대 해결책을 찾으려고 할 때를 의미합니다. 동적 프로그래밍은 솔루션이 존재하는 경우 문제의 최적 솔루션을 찾는 것을 보장합니다.
동적 프로그래밍의 정의에 따르면 먼저 더 간단한 하위 문제 모음으로 나누어 각 하위 문제를 한 번만 푼 다음 반복 계산을 피하기 위해 해당 솔루션을 저장하여 복잡한 문제를 해결하는 기술입니다.
예를 통해 이 접근 방식을 이해해 보겠습니다.
피보나치 수열의 예를 생각해 보세요. 다음 계열은 피보나치 계열입니다.
int를 문자열로 변환 C++
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
위 계열의 숫자는 무작위로 계산되지 않습니다. 수학적으로 아래 공식을 사용하여 각 용어를 작성할 수 있습니다.
F(n) = F(n-1) + F(n-2),
기본 값 F(0) = 0, F(1) = 1을 사용하여 다른 숫자를 계산하려면 위의 관계를 따릅니다. 예를 들어 F(2)는 다음과 같습니다. 에프(0) 그리고 에프(1), 이는 1과 같습니다.
F(20)을 어떻게 계산할 수 있나요?
F(20) 항은 피보나치 수열의 n번째 공식을 사용하여 계산됩니다. 아래 그림은 F(20)이 어떻게 계산되는지 보여줍니다.
자바 문자열 클래스
위 그림에서 볼 수 있듯이 F(20)은 F(19)와 F(18)의 합으로 계산됩니다. 동적 프로그래밍 접근 방식에서는 문제를 비슷한 하위 문제로 나누려고 합니다. 위의 경우 F(20)을 유사한 하위 문제, 즉 F(19)와 F(18)로 분류하는 경우 이 접근 방식을 따릅니다. 동적 프로그래밍의 정의를 요약하면 유사한 하위 문제는 두 번 이상 계산되어서는 안 된다는 것입니다. 그래도 위의 경우에는 하위 문제가 두 번 계산됩니다. 위의 예에서 F(18)은 두 번 계산됩니다. 마찬가지로 F(17)도 두 번 계산됩니다. 하지만 이 기법은 유사한 하위 문제를 해결한다는 점에서 꽤 유용하지만, 한 번 계산한 결과를 저장하는 것에 집착하지 않기 때문에 결과를 저장할 때 주의가 필요하며, 이로 인해 리소스 낭비가 발생할 수 있습니다.
위의 예에서 오른쪽 하위 트리의 F(18)을 계산하면 엄청난 리소스 사용량이 발생하고 전체 성능이 저하됩니다.
위 문제에 대한 해결책은 계산된 결과를 배열에 저장하는 것입니다. 먼저 F(16)과 F(17)을 계산하고 그 값을 배열에 저장합니다. F(18)은 이미 배열에 저장되어 있는 F(17)과 F(16)의 값을 합산하여 계산됩니다. F(18)의 계산된 값은 배열에 저장됩니다. F(19)의 값은 F(18)과 F(17)의 합을 사용하여 계산되며 해당 값은 이미 배열에 저장되어 있습니다. F(19)의 계산된 값은 배열에 저장됩니다. F(20)의 값은 F(19)와 F(18)의 값을 더하여 계산할 수 있으며, F(19)와 F(18)의 값은 모두 배열에 저장됩니다. F(20)의 최종 계산값은 배열에 저장됩니다.
동적 프로그래밍 접근 방식은 어떻게 작동하나요?
동적 프로그래밍이 수행하는 단계는 다음과 같습니다.
- 복잡한 문제를 더 간단한 하위 문제로 분해합니다.
- 이러한 하위 문제에 대한 최적의 솔루션을 찾습니다.
- 하위 문제의 결과(메모이제이션)를 저장합니다. 하위 문제의 결과를 저장하는 과정을 암기라고 합니다.
- 동일한 하위 문제가 두 번 이상 계산되도록 이를 재사용합니다.
- 마지막으로 복잡한 문제의 결과를 계산합니다.
위의 다섯 단계는 동적 프로그래밍의 기본 단계입니다. 다음과 같은 속성을 갖는 동적 프로그래밍을 적용할 수 있습니다.
자바와 비교
하위 문제와 최적의 하위 구조가 겹치는 문제입니다. 여기서 최적하부구조란 모든 하위 문제의 최적해를 단순히 결합함으로써 최적화 문제의 해를 얻을 수 있다는 의미이다.
동적 프로그래밍의 경우 중간 결과를 저장하므로 공간 복잡도는 증가하지만 시간 복잡도는 감소합니다.
동적 프로그래밍의 접근 방식
동적 프로그래밍에는 두 가지 접근 방식이 있습니다.
- 하향식 접근 방식
- 상향식 접근 방식
하향식 접근 방식
하향식 접근 방식은 암기 기법을 따르고, 상향식 접근 방식은 표 작성 방식을 따릅니다. 여기서 암기는 재귀와 캐싱의 합과 같습니다. 재귀는 함수 자체를 호출하는 것을 의미하고, 캐싱은 중간 결과를 저장하는 것을 의미합니다.
Java에서 arraylist 정렬
장점
- 이해하고 구현하는 것은 매우 쉽습니다.
- 필요할 때만 하위 문제를 해결합니다.
- 디버깅하기 쉽습니다.
단점
호출 스택에서 더 많은 메모리를 차지하는 재귀 기술을 사용합니다. 때때로 재귀가 너무 깊어지면 스택 오버플로 조건이 발생합니다.
더 많은 메모리를 차지하므로 전체 성능이 저하됩니다.
예제를 통해 동적 프로그래밍을 이해해보자.
int fib(int n) { if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); } < pre> <p>In the above code, we have used the recursive approach to find out the Fibonacci series. When the value of 'n' increases, the function calls will also increase, and computations will also increase. In this case, the time complexity increases exponentially, and it becomes 2<sup>n</sup>.</p> <p>One solution to this problem is to use the dynamic programming approach. Rather than generating the recursive tree again and again, we can reuse the previously calculated value. If we use the dynamic programming approach, then the time complexity would be O(n).</p> <p>When we apply the dynamic programming approach in the implementation of the Fibonacci series, then the code would look like:</p> <pre> static int count = 0; int fib(int n) { if(memo[n]!= NULL) return memo[n]; count++; if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); memo[n]="sum;" } < pre> <p>In the above code, we have used the memorization technique in which we store the results in an array to reuse the values. This is also known as a top-down approach in which we move from the top and break the problem into sub-problems.</p> <h3>Bottom-Up approach</h3> <p>The bottom-up approach is also one of the techniques which can be used to implement the dynamic programming. It uses the tabulation technique to implement the dynamic programming approach. It solves the same kind of problems but it removes the recursion. If we remove the recursion, there is no stack overflow issue and no overhead of the recursive functions. In this tabulation technique, we solve the problems and store the results in a matrix.</p> <p>There are two ways of applying dynamic programming:</p> <ul> <tr><td>Top-Down</td> </tr><tr><td>Bottom-Up</td> </tr></ul> <p>The bottom-up is the approach used to avoid the recursion, thus saving the memory space. The bottom-up is an algorithm that starts from the beginning, whereas the recursive algorithm starts from the end and works backward. In the bottom-up approach, we start from the base case to find the answer for the end. As we know, the base cases in the Fibonacci series are 0 and 1. Since the bottom approach starts from the base cases, so we will start from 0 and 1.</p> <p> <strong>Key points</strong> </p> <ul> <li>We solve all the smaller sub-problems that will be needed to solve the larger sub-problems then move to the larger problems using smaller sub-problems.</li> <li>We use for loop to iterate over the sub-problems.</li> <li>The bottom-up approach is also known as the tabulation or table filling method.</li> </ul> <p> <strong>Let's understand through an example.</strong> </p> <p>Suppose we have an array that has 0 and 1 values at a[0] and a[1] positions, respectively shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-2.webp" alt="Dynamic Programming"> <p>Since the bottom-up approach starts from the lower values, so the values at a[0] and a[1] are added to find the value of a[2] shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-3.webp" alt="Dynamic Programming"> <p>The value of a[3] will be calculated by adding a[1] and a[2], and it becomes 2 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-4.webp" alt="Dynamic Programming"> <p>The value of a[4] will be calculated by adding a[2] and a[3], and it becomes 3 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-5.webp" alt="Dynamic Programming"> <p>The value of a[5] will be calculated by adding the values of a[4] and a[3], and it becomes 5 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-6.webp" alt="Dynamic Programming"> <p>The code for implementing the Fibonacci series using the bottom-up approach is given below:</p> <pre> int fib(int n) { int A[]; A[0] = 0, A[1] = 1; for( i=2; i<=n; i++) { a[i]="A[i-1]" + a[i-2] } return a[n]; < pre> <p>In the above code, base cases are 0 and 1 and then we have used for loop to find other values of Fibonacci series.</p> <p> <strong>Let's understand through the diagrammatic representation.</strong> </p> <p>Initially, the first two values, i.e., 0 and 1 can be represented as:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-7.webp" alt="Dynamic Programming"> <p>When i=2 then the values 0 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-8.webp" alt="Dynamic Programming"> <p>When i=3 then the values 1and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-9.webp" alt="Dynamic Programming"> <p>When i=4 then the values 2 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-10.webp" alt="Dynamic Programming"> <p>When i=5, then the values 3 and 2 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-11.webp" alt="Dynamic Programming"> <p>In the above case, we are starting from the bottom and reaching to the top.</p> <hr></=n;></pre></0)></pre></0)>