Algorithm DP
1. DP 란?
DP는 다이나믹 프로그래밍 , 동적 계획법이라는 것은 하나의 큰 문제를 작은 문제로 나누어 푸는 방법이다.
하나의 작은 문제를 풀어 그 결과를 저장 하여 다시 큰 문제를 해결 할 때 사용한다.
사실 이름은 멋져 보이는데 그냥 멋있어 보이게 지은 것 뿐 다른 의미는 없다.
그냥 큰 문제를 작은 문제로 나누어 푸는 것 , 저장하면서 풀기 라는 의미이다.
2. DP는 왜 쓸 까?
사실 일반적으로 재귀 방식 또한 큰 문제를 작은 문제로 나누어 푸는 방법이다.
그러나 재귀 방식은 큰 문제를 풀기 위해 작은 문제를 풀어야 하는데
이 작은 문제를 풀기 위해 또 작은 문제를 풀어야 하는 경우가 생긴다.
풀었던 문제를 또 풀어야 하는 경우가 있다는 것 이다. 이는 이전 알고리즘 포스팅 재귀에서 설명했던 것이다.
이러한 문제를 해결하기 위해 DP를 사용한다.
3. DP 는 언제 쓸 수 있을까?
다음 두 가지 조건이 존재한다.
1. 겹치는 부분 문제
2. 최적 부분 구조
3.1. 겹치는 부분 문제
겹치는 부분 문제란 큰 문제를 작은 문제로 나누었을 때 작은 문제가 겹치는 경우를 말한다.
DP 는 기본적으로 문제를 나누고 그 문제를 풀어야 하는데 이때 나누어진 문제가 겹치는 경우가 생긴다.
이때 DP를 사용한다. 동일한 문제를 또 풀지 않기 위해 DP를 사용한다. 계속 풀었던 문제들이 나오는 경우를 말한다.
다시 말하자면 굳이 다시 쓸 것도 아닌데 저장해서 뭐하냐라는 것이다. 다시 쓸 일이 있어야 저장해서 쓰는 것 아닐 까?
3.2. 최적 부분 구조
최적 부분 구조란 큰 문제를 작은 문제로 나누었을 때 작은 문제의 답을 합치면 큰 문제의 답이 나오는 경우를 말한다.
이때 DP를 사용한다.
예를 들어보면 A - B 로 가는 경로의 최단 거리를 구하는 문제가 있다고 하자.
배열 경유지 = {C, D, E, F, G} 라고 하자.
이 때 어떤 경유지를 거쳐서 가는 것이 최단 거리인지 알아보기 위해
이 중 A-C/C-B 가 차 많은 경로 중 가장 짧다면 A-C/C-B 가 최단 거리가 된다.
이처럼 작은 문제의 답을 합치면 큰 문제의 답이 나오는 경우를 말한다.
4. DP 를 사용하는 방법
일반적으로 DP를 사용하기 전 아래 과정을 거친다.
- DP를 적용 할 수 있는 문제인가?
- 겹치는 부분 문제가 존재하는가?
- 최적 부분 구조가 존재하는가?
- 문제를 나눌 수 있는가?
- 문제를 나누었을 때 나눠진 문제가 겹치는가?
- 나눠진 문제의 답을 합치면 원래 문제의 답이 나오는가?
- 문제를 나누었을 때 나눠진 문제의 답이 원래 문제의 답이 되는가?
- 변수 간 관계를 찾는다. 점화식을 세운다.
- 피보나치의 경우를 들면 f(n) = f(n-1) + f(n-2) 이다.
- 의사코드 작성
- 코드 작성
5. DP 의 종류
DP 의 구현 방식은 총 두 가지 방법이 존재 한다.
- Top-Down - 재귀
dp[0] 에서 시작 하는 것이 아니라 dp[n] 에서 시작한다.
재귀 함수를 사용하여 dp[n] 을 구하기 위해서 dp[n-1] .. dp[0] 을 구한다. 순으로 재귀 함수를 호출한다.
이 때 동일한 계산이 반복적으로 나오게 되는데 이를 메모이제이션을 통해 해결한다.
- Bottom-Up - 반복문
dp[0] 에서 시작하여 dp[n] 을 구한다.
dp[n] 을 구하기 위해 dp[1] .. dp[n] 을 구한다. 순으로 반복문을 사용하여 구한다.
최하위 해답부터 차근차근 답을 도출한다. dp 하위 인덱스 부터 계산을 하여 누적 시켜 전체적인 큰 문제를 해결 하는 방식
Bottom-Up 방식은 반복문을 통해 점화식으로 결과를 도출해내 누적 그 값을 전이시켜서 최종적으로 전체 문제의 답을 구하는 방식이다.
5.1. Top-Down
public class Fibonacci {
public static void main(String[] args) {
int n = 10;
int[] dp = new int[n + 1];
System.out.println(fibonacci(n, dp));
}
private static int fibonacci(int n, int[] dp) {
if (n == 0 || n == 1) {
return n;
}
if (dp[n] != 0) {
return dp[n];
}
dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp);
return dp[n];
}
}5.2. Bottom-Up
public class Fibonacci {
public static void main(String[] args) {
int n = 10;
int[] dp = new int[n + 1];
System.out.println(fibonacci(n, dp));
}
private static int fibonacci(int n, int[] dp) {
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}둘 중 어떤 방식이 나은가?
Top-Down 방식은 재귀를 사용하기 때문에 함수 호출이 많이 일어나고 Bottom-Up 방식은 반복문을 사용하기 때문에 함수 호출이 적다.
이런 차이가 있지만 본질적으로 어떤 방식이 나은지에 대해서는 알 수 없다.
