[알고리즘 기법] 동적계획법 ( 다이나믹 프로그래밍 : DP ( Dynamic Programming ) )

 

◇  설명

  ◎  동적 계획법  ( DP ( Dynamic Programming ) )

    -  복잡한 큰 문제를 해결하기 위해 작은 문제로 분할할 때, 중복되는 작은 문제들을 한 번만 계산하도록 캐싱( 메모이제이션 )함으로써
       중복 계산을 피해 효율성을 높이는 알고리즘 설계 기법
    -  하향식( top-down ), 상향식( bottom-up )이 있음
    ┌  top-down 방식  :  큰 문제를 재귀적으로 계산
    └  bottom-up 방식  :  작은 부분부터 시작하여 이전의 결과를 이용하여 점진적으로 계산
    -  큰 문제를 작은 부분 문제들로 나눈다는 것은 분할정복법과 비슷하지만, 차이가 있음
     ∎  동적 계획법  --  부분 문제들이 같은 부분 문제에 의존함 ( -> 중복 계산이 많아짐 )
     ∎  분할 정복  --  부분 문제들이 서로 독립적이다. 연관이 없다

  ◎  메모이제이션 ( Memoization )
     :  계산 결과를 캐시에 저장하고, 저장된 값을 사용하는 것
      ( 단, 입력이 고정되어 있을 때 그 결과가 항상 같은 함수( 참조적 투명 함수 )의 경우에만 적용할 수 있음

  ◎  동적 계획법 레시피
    -  동적 계획법 알고리즘을 만드는 첫 단계는 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것
    1.  주어진 문제를 완전 탐색을 이용해 해결
    2.  중복된 부분 문제를 한 번만 계산하도록 메모이제이션 적용

 

◇  코드

  ex)  피보나치 수열

public class Test {  // 피보나치 수열
	
	static int[] cache;
    
	// 일반 재귀
    
	public static int fibonacci1( int n ) {
		if( n == 0 || n == 1  ) return n;
		return fibonacci1( n - 2 ) + fibonacci1( n - 1 );
	}
	
	// 동적 계획법
    
	public static int fibonacci( int n ) {  // top_down
		if( n == 0 || n == 1 ) return n;
		if( cache[n] != -1 ) return cache[n];
		return cache[n] = fibonacci( n - 2 ) + fibonacci( n - 1 );
	}

	public static int fibonacci2( int n ) {  // bottom_up
		if( n == 0 || n == 1 ) return n;
		int a = 0, b = 1, c = 0, i;
		for( i = 2; i <= n; i++ ) {
			c = a + b;
			a = b;
			b = c;
		}
		return c;
	}
    
	public static void main(String[] args) {
		
		int n = 5;
		
		cache = new int[n+1];
		
		for( int i = 0; i < n+1; i++ ) 
			cache[i] = -1;
		
		System.out.println( fibonacci( n ) );
	}
}

  ex)  이항 계수

public class Test {  // 이항 계수
	
	static int[][] cache;
    
	// 일반 재귀
	public static int bino1( int n, int r ) {
		if( n == r || r == 0 ) return 1;
		return bino1( n-1, r-1 ) + bino1( n-1, r );
	}
	
	// 동적계획법
	public static int bino( int n, int r ) {
		if( n == r || r == 0 ) return 1;
		if( cache[n][r] != -1 ) return cache[n][r];
		return cache[n][r] = bino( n-1, r-1 ) + bino( n-1, r );
	}
	
	public static void main(String[] args) {
		
		int n = 5, r = 3;
		
		cache = new int[n+1][r+1];
		
		for( int i = 0; i < n+1; i++ )
			for( int j = 0; j < r+1; j++ ) 
				cache[i][j] = -1;
		
		System.out.println( bino1( n, r ) );

		System.out.println( bino( n, r ) );
		
	    // 이항 계수 : n개 중 r개를 순서 없이 고는 경우의 수
	    // 기저사례  : n = r ( 모든 원소를 다 고르는 경우 ) or r = 0 ( 고를 원소가 없는 경우 )
	}
}

 

◇  출처

  -  설명  --  알고리즘 문제 해결 전략 ( 구종만 )
  -  코드  --  〃, 코딩 인터뷰 완전 분석 ( 게일 라크만 맥스웰 )