4강 다이나믹 프로그래밍 1 - 다이나믹 프로그래밍 소개

이번 강의에선 다이나믹 프로그래밍을 소개하고 어떤 방식이 있는지를 배웠다. 다음시간부터 문제를 풀어보기로 하고 우선 오늘 배운것을 정리해보도록 하겠다.

 

 

-------------------------------------------------------------------------------------------------------------------------------

 

-다이나믹 프로그래밍

다이나믹 프로그래밍은 동적 계획법이라고도 부른다. 큰 문제를 작은 문제로 나눠서 푸는 알고리즘으로 여기서 크기는 문제의 크기를 말한다. 다이나믹 프로그래밍은 2가지로 나눌 수 있다. 첫번째는 DP, 두번째는 분할정복이다. 이 두 개의 공통점은 큰 문제를 작은 문제로 나누어서 푼다는 것이다. 차이점은 DP는 작은 문제가 중복이 가능하여 작은 문제 하나를 풂으로써 큰 문제를 해결할 수 있고, 분할정복은 작은 문제가 중복이 가능하지 않다는 것이다. 

내가 참고하려고 첨부하는 내 필기 나 아이패드 샀당ㅎ_ㅎ

다이나믹 프로그래밍을 하려면 다음 두 가지 속성을 만족해야 풀 수 있다. 첫번째는 Overlapping Subproblem으로 겹치는 부분(작은) 문제가 있어야 하고, 두번째는 Optional Substrure로 최적부분구조로 이는 문제의 정답이 작은 문제의 정답을 통해 구할 수 있다!

 

이의 예시로 피보나치 수열 문제를 보자.

우선 Overlapping Subproblem을 통해 구하면 F0=0, F1=1, Fn=Fn-1 + Fn-2(n>=2)라는 식을 만족하게 된다. 여기서 n번째 피보나치 수를 구하는 문제(Fn)이 큰 문제, 뒤에 n-1번째와 n-2번쨰 피보나치 수를 구하는 문제가 작은 문제가 된다. 이를 통해서 문제의 크기는 상대적이라는 것을 알 수 있다.

참고하려고 넣은 슬라이드

 

위의 슬라이드를 보면 알 수 있듯이 큰 문제와 작은 문제를 같은 방법으로 풀 수 있기 때문에 주로 재귀함수를 사용한다. 

 

다음으로 Optional Substructure을 통해 구하면 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 

참고용 슬라이드2222222

Optional Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다. 

다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 위의 O.S를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같아서 한 번 구했으면 이를 어딘가에 저장해 놓고 다음부터는 그 값을 불러서 사용한다. 이는 영어로 메모한다고 해서 Memoization이라고도 한다. 캐시의 개념과 비슷하게 생각하면 된다~~

 

피보나치 수를 예시로 시간 복잡도를 계산한다면 그냥 재귀함수를 통해 구하면 함수가 한번 호출될 때마다 2개씩 함수가 호출되니까 함수의 깊이를 N이라고 하면 O(2^N)이 된다. 만약 DP를 통해서 한번 구한 답을 저장하는 방식으로 구한다면, 이는 모든 문제를 1번씩 푸는게 된다. 따라서 시간복잡도는 문제의 개수 * 문제 1개를 푸는 시간이 된다. 여기서 문제의 개수는 N개이고, 문제 1개를 푸는 시간은 함수의 시간복잡도와 같으므로 O(1)이 되어 최종 시간복잡도는 O(N)이 된다. 따라서 DP를 사용하는게 훨씬 효율적이라고 할 수 있게된다!! 마! 이게 다이나믹이다~

 

다이나믹의 구현 방식에는 Top-down과 Bottom_up 두 가지 방법이 있다. 우선 Top-down은 큰 문제부터 문제를 쪼개가면서 작은 문제를 만들고 다시 합쳐가면서 원래 문제를 푸는 방식이다. 이는 주로 재귀함수를 통해 구현한다. Bottom-up은 작은 문제를 모아서 큰 문제 하나를 만들고, 이 과정을 반복해서 쌓아올리는 방식으로 주로 반복문을 통해 구현한다. 이 떄 두 방법의 시간차이는 알 수 없다. 근데 재귀함수를 사용하면 내부 스택을 사용하기 떄문에 스택 오버플로우가 발생할 수도 있다.(완전 진짜 가아아끔) 근데 둘 다 시간복잡도는 O(N)이다. 

 

 

<1003번 / 피보나치 수>

이 문제는 피보나치 수를 구하는 문제로 다이나믹 프로그래밍과 일반 재귀함수의 속도 차이를 확인할 수 있다. 나는 처음엔 그냥 재귀함수로 풀었는데 답은 맞지만 시간초과가 나왔다. 아래는 재귀함수로 구현한 코드이다.

 

-Overlapping Subproblem

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <stdio.h> using namespace std; int zero; int one; int fibonacci(int n) {     if (n == 0)     {         zero++;         return 0;     }     else if (n == 1)     {         one++;         return 1;     }     else     {         return fibonacci(n - 1) + fibonacci(n - 2);     } } int main() {     int t;     scanf("%d", &t);     while (t--)     {         int n;         scanf("%d", &n);         zero = 0;         one = 0;         fibonacci(n);         printf("%d %d\n", zero, one);     }     return 0; }

cs

이를 다이나믹 프로그래밍을 통해 구현한다. 이는 이미 구한건 저장해놓고 저장한 수를 불러오는 것이다. 그러면 연산의 수가 줄면서 시간이 현저히 감소된다. 또한 여기서 주목해야할 점이 있는데, 바로 이것이다. 아래의 표를 보면 0이 나오는 횟수는 n-1번째 수고, 1이 나오는 횟수는 n번째 수가 된다. 이를 통해서 쉽게 해결할 수 있다.

피보나치 수열 규칙

정신 놓고 풀다가 한 다섯번 틀리고 겨우 맞음;;; 저 위의 방법 사용하고, 0이랑 1일때는 예외처리해서 출력한다. 피보나치 구할떄도 0이랑 1을 예외처리해서 memo배열에 저장하고 한번 저장한 배열은 다시 계산하지 않도록 구현하였따. 이랬더니 0ms 시간이 나왔다. 이게 모라고 5번씩이나....;;;;;

 

-Optional Substructure

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <stdio.h> using namespace std; int memo[41]; int fibonacci(int n) {     if (n == 0)     {         memo[0] = 0;         return 0;     }     else if (n == 1)     {         memo[1] = 1;         return 1;     }     else     {         if (memo[n] != 0)             return memo[n];         memo[n] = fibonacci(n - 1) + fibonacci(n - 2);         return memo[n];     } } int main() {     int t;     scanf("%d", &t);     while (t--)     {         int n;         scanf("%d", &n);         if (n == 0)             printf("%d %d\n", 1, 0);         else if (n == 1)             printf("%d %d\n", 0, 1);         else         {             fibonacci(n);             printf("%d %d\n", memo[n-1], memo[n]);         }     }     return 0; }

cs

 

이제 다음 강의에서는 문제를 풀면서 익혀보도록 하자~><