동적 프로그래밍은 이름이 조금 이상한데요. 프로그래밍은 컴퓨터 프로그래밍이라는 뜻이 아니라 테이블을 만든다는 뜻입니다. 그리고 전혀 다이나믹하지도 않습니다. 그래서 어떤 서울대 교수님은 동적 프로그래밍 대신 기억하기 프로그래밍이라는 용어를 쓰기도 합니다.
재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법입니다. 메모이제이션이 동적 프로그래밍 중 하나입니다.
알고리즘을 짤 때 분할정복 기법을 사용하는 경우가 많습니다. 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법인데요. 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 동적 프로그래밍입니다.
기존의 전수조사에서의 재귀설계에서 매 호출하다 줄어드는것을 기준으로 기저사례를 정하였다면 동적설계에서는 memoization리스트를 하나두어 해당 조건을 만족하면 그것을 기저사례로 설정하여 더 이상아래로 내려가지 않아도 되게한 것이다!!! 즉, 기저사례를 기존의 하나에서 두개로 늘린것이다! 이게 가장 중요한점!!
기존의 전수조사에서의 재귀설계에서 매 호출하다 줄어드는것을 기준으로 기저사례를 정하였다면
동적설계에서는 memoization리스트를 하나두어 해당 조건을 만족하면 그것을 기저사례로 설정하여
더 이상아래로 내려가지 않아도 되게한 것이다!!! 즉, 기저사례를 기존의 하나에서 두개로 늘린것이다!
이게 가장 중요한점!!
def cuttingStickTd(p,n,m):#Top-down Memoization방식
if(m[n]>=0):
return m[n]
if n==0:
q=0
else:
q=-1
for i in range(1, n+1):
q=max(q, p[i]+cuttingStickTd(p, n-i, m))
m[n]=q
return q피보나치 수열
피보나치수열은 제2항 까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수가 반복되는 수열이다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
이러한 피보나치수열을 구현할 때는 보통 재귀를 통해 표현하게 된다. c언어에서는 아래와 같이 구현 할 수 있다.
|
1
2
3
4
5
6
|
int fibo(int n){
if (n<=2)
return 1;
else
return fibo(n-1) + fibo(n-2);
}
|
cs |
def ordinaryFibo(n):
if(n<=2):
return 1
else:
return ordinaryFibo(n-1)+ordinaryFibo(n-2)
print('Ordinary Fibo', ordinaryFibo(10))
이렇게 재귀를 통해 피보나치 수열을 구하게 되면 중복 연산이 많아져 매우 비효율적이다. 예를 들어 fibo(5)를 구한다고 하자.
재귀를 통한 피보나치 수열
fibo(5)를 구할 때 위와 같은 과정을 거쳐 구하게 된다. 그림을 보면 fibo(1), fibo(2), fibo(3) 연산이 중복되는 것을 볼 수 있다. 만약 fibo(1), fibo(2), fibo(3) 연산의 값을 어딘가에 저장해 놓는다면, 중복해서 연산하지 않아도 될 것이다.
동적 계획법(Dynamic Programming)
동적 계획법은 복잡한 문제를 여러 개의 간단한 문제(하위 문제)로 나누어 풀고, 그것을 결합하여 최종적인 문제를 해결하는 것이다. 이때 각 하위 문제들의 답을 저장해놓고 같은 하위 문제가 나타난다면 미리 구한 답을 이용하면 된다. 분할 정복(Divide and Conquer) 방식과 비슷하지만 분할 정복은 하위 문제가 중복되지 않는다는 점이 다르다.
메모이제이션(Memoization)
동일한 문제를 반복해야 할 경우, 미리 계산해서 저장해 둔 결과를 활용하여 중복 연산을 줄이는 방식을 메모이제이션이라고 한다. 동적 계획법은 중복되는 하위 문제를 메모이제이션을 이용해 효율적으로 해결할 수 있다.
동적 계획법을 이용한 피보나치수열 해결
동적 계획법은 Top-down 방식과 Bottom-up 방식 두 가지 접근법이 존재한다. 이를 피보나치수열을 예로 들어서 fibo(n)을 구하는 방식을 두 가지로 나누어보자.
1. Top-down 방식
1) 큰 문제를 작은 문제(하위 문제)로 나눈다.
2) 작은 문제(하위 문제)를 푼다.
3) 작은 문제의 답을 결합해 최종 문제를 해결한다.
피보나치수열을 예로 들자면 아래와 같은 과정을 거치게 된다.
1) 큰 문제를 작은 문제(하위 문제)로 나눈다.
- fibo(n-1)과 fibo(n-2) 로 문제를 나눈다.
2) 작은 문제(하위 문제)를 푼다.
- fibo(n-1) 과 fibo(n-2)를 구한다. 이때 이미 구한 값이라면 저장한 값을 이용한다. 구해놓지 않은 값이라면 이를 메모이제이션 배열에 저장해 놓는다.
3) 작은 문제의 답을 결합해 최종 문제를 해결한다.
- fibo(n-1)과 fibo(n-2) 값을 더해 fibo(n)을 구한다.
c언어로 이를 구현하면 아래와 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <stdio.h>
int dp[100] = {0,}; // 하위 문제 답을 저장할 메모이제이션 배열
int fibo(int n) {
if (n <= 1) {
return n;
} else {
if (dp[n] > 0) { // 해당 문제의 답이 존재
return dp[n];
}
dp[n] = fibo(n-1) + fibo(n-2);
return dp[n];
}
}
int main(){
printf("%d", fibo(5));
return 0;
}
|
cs |
m=[-1]*30
def fiboTd(m,n):
if(m[n]>=0):
return m[n]
if(n<=2):
return 1
m[n]=fiboTd(m, n-1)+fiboTd(m, n-2)
return m[n]
print('정답: ',fiboTd(m, 10))
print('DP의 값: ', m)#배열이 아닌 map을 memoization으로 사용한 예(복습의 차원에서 dict()함수와 대응됨 map()은 2번째인자를
#1번째인자로 대응시키는 일반함수이지만 dict()는 자료구조 함수임
memo={1:1,2:1}
def fibo(n):
if(n in memo):
return memo[n]
if(n<=2):
return n
memo[n]=fibo(n-1)+fibo(n-2)#방정식은 디자인을 돕는다(무하마드 said)
return memo[n]
print(fibo(10))
이렇게 Top-down 방식으로 구현하면 메모이제이션의 장점을 제대로 활용할 수 없다. 연산 수가 줄어들어 기존의 방식보다는 효율적이지만 재귀적인 함수 호출로 인한 Overhead가 여전히 존재하므로 비효율적이다.
2. Bottom-up 방식
Bottom-up 방식은 작은 문제들부터 해결하여 이를 결합해 큰 문제를 해결하는 방식이다.
1) 작은 문제들부터 푼다.
2) 작은 문제들의 답을 이용해 큰 문제를 푼다.
3) 이를 반복해 최종 문제를 푼다.
피보나치수열을 예로 들자면 아래와 같은 과정을 거치게 된다.
1) 작은 문제들부터 푼다.
- fibo(i-1) , fibo(i-2) 값을 나타낼 dp [i-1] , dp [i-2]를 구한다.
2) 작은 문제들의 답을 이용해 큰 문제를 푼다.
- dp[i-1] + dp[i-2] 를 이용해 dp [i]를 구한다.
3) 이를 반복해 최종 문제를 푼다.
- 이를 반복해 dp [n]을 구한다.
c언어로 이를 구현하면 아래와 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <stdio.h>
int dp[100] = {0,}; // 하위 문제 답을 저장할 메모이제이션 배열
int fibo(int n) {
dp[0] = 0;
dp[1] = 1;
int i;
for (i=2; i<=n; i++) { // 2부터 시작해서 n까지 반복
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
int main(){
printf("%d", fibo(5));
return 0;
}
|
cs |
def fiboBu(m,n):
m[1]=1
m[2]=1
for i in range(3,n+1):
m[i]=m[i-1]+m[i-2]
fiboBu(m, 8)
print(m)이렇게 위의 Tabulation을 통해 교수님이 하신 말씀
" 동적프로그래밍의 핵심은 점화식을 세우는 것입니다. 점화식만 세우면 동적프로그래밍의 코딩은 매우 수월해 집니다.(여기서의 점화식은 dp[i]=dp[i-1]+dp[i-2])
동적프로그래밍이 어려운 이유는 문제에서 점화식을 세우는 것이 익숙치 않기 때문입니다. 그리고 이 점화식의 구현은 대부분 재귀호출이 아닌 반복문입니다.(Memoization에서 Tabulation으로 바뀌면서 재귀가 반복문으로 바뀌었다!)"
이 증명됨.
이렇게 메모이제이션(보통 Memoization과 Tabulation의 용어구분을 전혀 하지 않는거같음) 배열을 이용해 bottom-up 방식으로 피보나치수열을 풀게 되면 재귀 함수 호출로 인한 overhead 가 없고, 연산 수도 줄어들어 효율적이다.
'알고리즘 > DP(Dynamic programming, 동적프로그래밍)' 카테고리의 다른 글
| [백준] 2293 동전1 (0) | 2023.05.31 |
|---|---|
| [백준] 11066번: 파일 합치기 (0) | 2023.05.20 |
| [백준] 9251번 : LCS(Longest Common Subsequence) (0) | 2023.05.19 |
| 배낭채우기 문제 (0) | 2023.02.28 |
| DP 기본문제인 막대기 자르기(백준에 없는문제) (0) | 2023.02.14 |
