Menu

Subscribe

[Algorithm] 동적 계획법(DP)

HEESOO on Algorithm

동적 계획법(Dynamic Programming)

1. 기본 개념

  • 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다(작은 문제->큰 문제도 가능).
  • Top-Down 방식
  • 큰 문제를 작은 문제로 나눠서 작은 문제를 푼다.
  • 재귀 호출로 구현한다.
  • 함수 호출에 대한 오버헤드가 발생한다.
  • 큰 문제로부터 빠른 속도로 최적의 해를 도출 가능하다.
  • 메모이제이션(Memorization, 반복되는 결과를 메모리에 저장해서 중복 호출 시 한 번 더 계산하지 않고 메모리 값을 재활용하는 방식) 기법을 사용한다.
  • 실행 시간과 메모리를 trade-off한다.
  • Bottom-Up 방식
  • 문제를 크기가 작은 문제부터 조금씩 크게 만들면서 답을 계산한다.
  • 반복문을 사용한다.
  • 모든 문제를 해결해야한다.

2. 코드

  • Top-Down
1
2
3
4
5
6
7
8
9

/**
 *
 * @author HEESOO
 *
 */
/*...*/
public static void method(...){
    func(n)=func(n-1)+func(n-2);
/*...*/
  • Bottom-Up
1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 *
 * @author HEESOO
 *
 */
/*...*/
public static void method(...){
    dp[1]=1;
    dp[2]=1;
    for(int i=2;i<n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
/*...*/

4. 참고