다이나믹프로그래밍1 - subproblems

GeekforGeek-dp1 페이지를 해석한 포스트입니다.

 

다이나믹 프로그램에서 부문문제 오버랩핑 특성

다이나믹 프로그래밍은 주어진 복잡한 문제를 부분문제로 나눠 문제를 해결하고 같은 결과를 다시 계산하는 것을 피하기 위해 부문문제의 답을 저장하는 알고리즘 패러다임이다. 다음은 다이나믹 프로그래밍으로 풀 수 있는 문제의 두가지 특징이다.

이번 포스트에서는 첫번째 특징( Overlapping Subproblems)을 자세히 살펴볼 것이다. 두번째 특징은 다음장에서 알아볼 것이다.

1. Overlaping Subproblems
2. Optimal Substructure

 

1) Overlapping Subproblems:

분할 정복처럼, 다이나믹 프로그래밍은 부분문제의 해결책을 조합한다. 다이나믹 프로그램은 주로 반복되는 부문문제의 답이 계속해서 필요할 때 사용된다. 다이나믹 프로그래밍에서 부문문제의 답은 테이블에 저장되고 다시 계산할 필요가 없다. 그래서 다이나믹 프로그래밍은 공통의 부문문제가 없을 때는 유용하지 않다. 왜냐하면 부문문제의 답이 다시 사용될 필요가 없다면 저장할 필요가 없기 때문이다. 예를 들어, 이분 탐색 문제에서 공통의 중복문제가 없다. 피보나치 수열을 예로 들어보면, 재사용되는 많은 중복문제들이 있다.

​x
int fib(int n){
    if( n <= 1 )
    return n;
    return fib(n-1) + fib(n-2);
}

fib(5) 실행의 재귀트리

xxxxxxxxxx
                              
                         fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

위 트리에서 fib(3)가 두번 사용도니 것을 알 수 있다. 만약 fib(3)의 값을 미리 저장해 놓았다면, 다시 계산하는 대신에 저장된 값을 사용할 수 있다. 다시 사용할 수 있도록 값을 저장하는 두가지 방법이 있다.

a) Memoization (Top Down)

b) Tabulation (Bottom up)

a) Memoization: Memoization은 재귀적인 방법과 비슷하지만, 값을 계산하기전에 미리 저장된 값을 살펴본다는 차이점이 있다. 먼저 lookup 배열을 NIL 값으로 초기화 한다. 부문문제의 답이 필요할 때 먼저 lookup 배열을 확인한다. 만약 미리 계산된 값이 있다면, 그 값을 반환하고 그렇지 않으면 값을 계산해서 결과 값을 해당 배열에 저장한다. 그러면 이 값은 나중에 다시 사용된다.

다음은 Memoization 방법의 피보나치 수열이다.

x
​
/* Java program for Memoized version */
public class Fibonacci 
{ 
  final int MAX = 100; 
  final int NIL = -1; 
  
  int lookup[] = new int[MAX]; 
  
  /* Function to initialize NIL values in lookup table */
  void _initialize() 
  { 
    for (int i = 0; i < MAX; i++) 
        lookup[i] = NIL; 
  } 
  
  /* function for nth Fibonacci number */
  int fib(int n) 
  { 
    if (lookup[n] == NIL) 
    { 
      if (n <= 1) 
          lookup[n] = n; 
      else
          lookup[n] = fib(n-1) + fib(n-2); 
    } 
    return lookup[n]; 
  } 
  
  public static void main(String[] args) 
  { 
    Fibonacci f = new Fibonacci(); 
    int n = 40; 
    f._initialize(); 
    System.out.println("Fibonacci number is" + " " + f.fib(n)); 
  } 
  
} 
// This Code is Contributed by Saket Kumar 

 

b) Tabulation (Bottom up): Tabulated 프로그램은 아래에서 부터 테이블을 채워나가고 마지막 값을 반환한다. 같은 피보나치 수열을 예를 들면, 먼저 fib(0)을 계산하고 fib(1), fib(2) 그리고 fib(3)를 계산한다. 문자그대로 아래에서부터 부분문제를 해결한다.

아래는 Bottom up 방식의 피보나치 수열 코드이다.

xxxxxxxxxx
​
/* Java program for Tabulated version */
public class Fibonacci 
{ 
  int fib(int n) 
  { 
    int f[] = new int[n+1]; 
    f[0] = 0; 
    f[1] = 1; 
    for (int i = 2; i <= n; i++) 
          f[i] = f[i-1] + f[i-2]; 
    return f[n]; 
  } 
  
  public static void main(String[] args) 
  { 
    Fibonacci f = new Fibonacci(); 
    int n = 9; 
    System.out.println("Fibonacci number is" + " " + f.fib(n)); 
  } 
  
} 
// This Code is Contributed by Saket Kumar 

앞서 살펴본 두가지 방법 모두 부붐문제의 답을 저장한다. 메모이제이션은 필요한 값만 체오는 반면 Tabulated 방식은 첫번째 요소부터 시작하여 하나 하나 모든 요소를 저장한다. Tabulated 방법과는 달리 lookup 테이블의 모든 요소는 메모이제이션 방식에서는 채워질 필요가 없다. 예를 들어 lcs 문제의 메모이제이션 방식은 모든 요소를 구할 필요가 없다.

재귀적인 방법과 비교해서 메모이제이션과 테뷸레이션 방법으로 최적화를 보려면, 40번째 피보나치 수열을 계산해보며 소요시간을 비교해 보아라.

재귀적인 방법이 두가지 다이나믹 프로그래밍 기술에비해 더 많은 시간이 소요된다.

이제 최적화 하부구조 특징을 배울 것이며 다이나믹 프로그래밍의 더 많은 예제를 풀어볼 것이다.