1. DP(동적 계획법)란?
- 동적 계획법은 그리디 알고리즘과 같이
최적화 문제를 해결하는 알고리즘이다.- 동적 계획법은 먼저 작은 부분 문제들의 해를 구하고 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법이다.
2. 메모이제이션(Memoization)
메모이제이션이란 한 번 계산한 결과를 메모리 공간에 메모하는 기법으로, 동적 계획법의 핵심이 되는 기술이다.
- 처음 계산하는 경우 결과를 기록하고, 이미 계산한 값인 경우 이전에 기록된 값을 반환하여 중복계산을 방지한다.
- 값을 기록해 놓는다는 점에서 캐싱(Cashing)이라고도 한다.
✨ 즉, Dp는 메모이제이션을 통해 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
3. DP 사용 조건
동적 계획법을 적용하려는 문제는 필히 다음과 같은 요건을 가지고 있어야 한다.
☑️ 중복 부분문제 구조(Overlapping subproblems)
- DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해(Optimal Solution)를 이용하여 순환적으로 큰 문제를 해결한다.
- DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데 이미 해결된 작은 문제들의 해들을 메모이제이션을 통해 DP 테이블에 저장하게 된다.
- 결과 저장용 리스트를 DP 테이블이라고 부른다.
- 이렇게 저장된 해들을 다시 필요할 때마다 table 참조를 통해 중복 계산을 방지한다.
☑️ 최적 부분문제 구조(Optimal substructure)
- 동적 계획법을 적용하기 위해서는 주어진 문제가
최적화의 원칙을 만족해야한다. 최적화의 원칙이란 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다.- 만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법을 적용할 수 없다.
☑️ 경우의 수 문제구조
4. DP 구현 방법
DP는 '하향식'이나 '상향식'을 사용하여 구현 가능하다.
최적해 구조의 특성을 파악하여 문제를 부분 문제로 나눈 후, 최적해의 값을 📝관계식(점화식)으로 정의한다.
☑️ Top-Down
- 위에서 아래로 접근하는 방법(하향식)
- 재귀 함수 활용
- 큰 문제에서 부분 문제로 쪼개가며, 재귀 호출을 이용하여 해결하는 방법
☑️ Bottom-Up
- 아래에서 위로 접근하는 방식(상향식)
- for문을 활용
- 부분 문제에서부터 문제를 풀어가며 점차 큰 문제를 풀어가는 방법
- DP의 전형적인 형태
5. 예제 코드(피보나치 수열)
💻 아래 코드는 피보나치 수열을 일반 재귀 함수, DP 햐향식, DP 상향식으로 구현한 코드이다.
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static long callCnt1,callCnt2, callCnt3;
// 1. 일반 재귀로 구현
private static int fibo1(int n) {
callCnt1++;
//기저
if(n<=1) return n;
// 유도
return fibo1(n-1)+fibo1(n-2);
}
// 2. DP(Top-Down)로 구현
private static long[] memo; // 저장 table
private static long fibo2(int n) {
callCnt2++;
// 계산하지 않은 값인 경우
if(memo[n]==-1) {
memo[n]=fibo2(n-1)+fibo2(n-2);
}
// 이미 계산한 값인 경우
return memo[n];
}
// 3. DP(Bottom-Up)로 구현
private static long[] memo2; // 저장 table
private static long fibo3(int n) {
memo2=new long[n+1];
memo2[0]=0;
memo2[1]=1;
for(int i=2;i<=n;i++) {
callCnt3++;
memo2[i]=memo2[i-1]+memo2[i-2];
}
return memo2[n];
}
public static void main(String args[]) throws IOException{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
memo=new long[n+1];
Arrays.fill(memo, -1); // 메모되지 않은 상태로 초기화
memo[0]=0; memo[1]=1;
System.out.println(fibo1(n));
System.out.println("재귀 계산 횟수: "+callCnt1);
System.out.println("=========================");
System.out.println(fibo2(n));
System.out.println("Top-Down 계산 횟수: "+callCnt2);
System.out.println("=========================");
System.out.println(fibo3(n));
System.out.println("Bottom-Up 계산 횟수: "+callCnt3);
}
}
📌위에 결과 화면을 보면 10을 입력했을 때 각각의 계산 횟수가 모두 다른 것을 확인할 수 있다.
성능: 상향식>햐향식>재귀
