Algorithm, DP
DP(다이나믹 프로그래밍)
- 주어진 문제를 여러 개의 부분문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다
- dp는 겹치는 문제가 발생하기 때문에 메모제이션 등이 필요하다
- 메모제이션 : 함수의 결과를 저장하는 장소를 마련해두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법.
[예시]
피보나치 수열을 구현해 보자. fibonacci
static int org_fibonacci(int n) {
call[n]++;
if(n==0) return 0;
if(n==1) return 1;
return fibonacci(n-2) + fibonacci(n-1);
}
- 문제점 : n이 30을 넘어가서 40정도의 수치가 되면 컴퓨터는 바로 답을 구하지 못한다.
- 분석 : n이 작은 함수 호출로 갈수록 그 횟수가 점점 증가한다. 비보나치 결과 이를 그림으로 그려보면 이러하다. 피보나치2 그림의 두 부분을 살펴보면 구조가 완전히 동일하고 당연히 f(3)의 값도 같다. 즉, 한번 계산하면 충분할 값을 호출할 때마다 계속 부르고 있어 불필요한 시간낭비를 하고 있다는 것이다.
해결방법
- 메모제이션(memoization) 기법을 사용한다
- 계산한 적이 있다면 추가 재귀 호출 없이 그 값을 바로 리턴해준다
1. 탑다운 형식
static int fibonacci(int n) {
if(n==0) return 0;
if(n==1) return 1;
// 이미 값을 계산한 적이 있다면 그 값을 바로 리턴
if(dp[n] != -1) return dp[n];
// 아니라면 계산해서 dp리스트에 넣어 보존
dp[n] = fibonacci(n-2) + fibonacci(n-1);
return dp[n];
}
2. 바텀업 형식
static void fibonacci2(int n) {
Arrays.fill(dp, 0);
dp[1] = 1;
for (int i=2; i<=n; i++)
dp[i] = dp[i-1]+dp[i-2];
System.out.println(dp[n]);
}