[DP] 다이나믹 프로그래밍
개념
큰 문제를 작은 문제로 나눠서 풀고, 다시 원래 큰 문제를 푸는 알고리즘
Dynamic Programming이라는 이름은 그냥 멋있어서 붙혀졌다고 합니다.
큰 문제를 작은 문제로 나눠서 푸는 두 개의 알고리즘
DP : 작은 문제가 여러번 나온다. 여러번 나오는 문제의 정답이 항상 같다는 것을 이용해 각각의 문제를 한 번씩 푼다.
분할 정복 알고리즘 : 모든 작은 문제가 한 번씩 나와서 그냥 모든 문제를 한 번씩 푼다.
DP의 두가지 속성
- Overlapping Subproblem : 부분 문제가 겹친다. 부분 문제를 여러번 구해야하는 경우가 발생한다.
- Optiaml Substructure : 부분 문제의 정답이 항상 같다. 작은 동일한 문제가 나오면 이 두 문제의 정답은 항상 같아야 한다. 따라서 부분 문제의 값을 저장해어서 실행시간을 줄인다.
Overlapping Subproblem
피보나치 수
$F_{0} = 0$
$F_{1} = 1$
$F_{n} = F_{n-1} + F_{n-2}$
- 크기 n 문제를 n-1과 n-2 문제로 나워서 풀고 이들을 더해서 큰 문제를 푼다.
- 다음으로 작은 문제들이 겹치는지를 체크
- n-1 문제를 풀 때 n-2와 n-3을 구해야 함
- n-2 문제를 풀 때 n-3와 n-4을 구해야 함
- n-3 문제가 중복해서 발생함.
- 즉, 큰 문제를 작은 문제로 쪼갤 수 있고 큰 문제와 작은 문제를 푸는 방법이 같다.
Optiaml Substructure
문제의 정답을 작은 문제의 정답에서 구할 수 있다. 1
서울에서 부산갈 때 제일 빠른 길 (가정): 서울 -> 대전 -> 대구 -> 부산
대구에서 부산갈 때 제일 빠른 길 : 대전 -> 대구 -> 부산
알고보니 울산도 갈 수 있는 도시였다고 할 때,
대구에서 부산갈 때 제일 빠른 길 : 대전 -> 울산 -> 부산 으로 바뀌었다. 이런 경우는 없음. 즉, 큰 문제의 정답을 구할 때 작은 문제의 정답이 꼭 사용 되어야한다.
10 번째 피보나치 수를 구하면서 4번째 피보나치 수를 구해야한다.
9 번째 피보나치 수를 구하면서 4번째 피보나치 수를 구해야한다.
4 번째 피보나치 수를 구하면서 4번째 피보나치 수를 구해야한다.
4 번째 피보나치 수는 변하지 않는다.
-> 한 번 작은 문제를 풀어두고 이 문제의 정답을 어디에 저장해두자!
피보나치 수
메모를 하지 않는다면, 시간 복잡도 $O(2^{n})
int fibo(int n){
if(n <= 1){
return n;
}else{
return fino(n-1) + fibo(n-2);
}
}
메모를 한다면, 시간 복잡도는 $O(N)$
int memo[100];
int fibo(int n){
if(n <= 1){
return n;
}else{
if(memo[n]> 0){
return memo[n];
}
memo[n] = fino(n-1) + fibo(n-2);
return memo[n];
}
}
시간 복잡도
모든 문제는 한 번씩만 푼다. 함수 호출은 n번 이루어 진다. 함수 호출은 메모에 적혀있지 않아서 메모를 구하는데 사용되는 호출을 의미한다. 즉, 함수 호출 시간은 $O(1)$이 걸린다. 따라서 전체 시간 복잡도는 $O(n)$이다.
다이나믹을 푸는 두 가지 방법
Top-down : 재귀함수
큰 문제를 점점 쪼개면서 작은 문제로 가는 것. 이전에 했던 방법.
int fibo(int n){
if(n <= 1){
return n;
}else{
return fino(n-1) + fibo(n-2);
}
}
Bottom-up : for문
작은 문제가 점점 합쳐지면서 큰 문제를 풀게 되는 것
- 문제를 크기가 작은 문제부터 차례대로 푼다.
- 문제의 크기를 조금씩 크게 만든다.
- 작은 문제를 풀면서 왔기 때문에 큰 문제는 항상 풀 수 있다.
int d[100];
int fibonacci(int n) {
d[0] = 0;
d[1] = 1;
for (int i=2; i<=n; i++) {
d[i] = d[i-1] + d[i-2];
}
return d[n];
}
? Bottom-up?
대부분 Top-down으로도 Bottom-up으로도 풀 수 있다. 전자가 stack에 넣고 빼야해서 느릴 수도 있고, 후자가 전자는 필요없는 모든 경우를 다 풀어야해서 느릴 수도 있다. 일반적으로 뭐가 더 좋은지는 정해져있지 않고, 전자와 후자로 풀 떄 모두 시간 복잡도는 같게 나올 것이다.
문제 풀이 전략 1 : Bottom-up
- 문제를 크기가 작은 문제부터 차례대로 푼다.
- 문제의 크기를 조금씩 크게 만든다.
- 작은 문제를 풀면서 왔기 때문에 큰 문제는 항상 풀 수 있다.
답을 구하는 점화식을 정의하고, 점화식을 코딩한다.
- D[N]을 구해야한다는 것을 정한다.
- N을 N-1과 N-2로 나누는 법을 생각한다.
- D[N] = D[N-1] + D[N-2]를 짠다.
문제 풀이 전략 2 : Top-down
- 문제에서 구하고자 하는 답을 문장으로 나타낸다.
- EX ) N 번째 피보나치 수
- Bottom-up : 이제 이 문장에 나와있는 변수의 갯수만큼 메모하는 배열을 만든다.
- Top-Down : 이제 이 문장에 나와있는 변수의 갯수 = 재귀호출 인자의 갯수
- 문제를 작은 문제로 나누고, 수식을 이용해서 문제를 표현해야 한다.