5. 다이나믹 프로그래밍(동적 계획법)

개념

• 정의: 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않는 방법
  • 즉, 메모리를 적절히 사용하여 수행 시간 효율성을 늘리는 방법
• 사용 조건: 점화식을 가진 구조
  • 최적 부분 구조: 큰 문제를 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결할 수 있어야함
  • 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결해야함
• 언제 생각? : 여러가지 선택지가 있는데 그리디 기법으로 안풀리면 한번 생각해보기
  • 단, i번째 선택지가 i-1번째 선택지에 영향을 받아야함
  • 즉, 이전 선택을 계속 누적해서 가는 문제들

 

다이나믹 프로그래밍 vs 분할 정복

• 공통점: 두 방법 모두 최적 부분 구조를 가진다.
• 차이점: 
  • 다이나믹 프로그래밍: 동일한 작은 문제를 반복적으로 해결
  • 분할 정복: 동일한 작은 문제를 해결x

 

예시

피보나치 수열

public static int fibo(int x){
	if( x == 1 || x == 2 ){
    	return 1;
    }
    
    return fibo(x-1) + fibo(x-2);

}

 

위 처럼 단순 재귀 함수로 피보나치 수열을 해결한다면 지수 시간 복잡도가 발생함

why?: 앞선 항을 계산하기 위해 중복되는 작은 문제들을 다 계산해야하기 때문

 

구현 방법

결과 저장용 리스트 DP 테이블을 이용해서 진행

 

상향식(bottom-up)

• 반복문을 이용해서 구현하는 방법
  • 전형적으로 상향식 방법을 많이 이용
• 시간 복잡도: O(N)

static int[] dp;

public static void main(String[] args){
	dp = new int[n+1];

	dp[1] = 1;
    dp[2] = 1;

	for(int i=3; i<=n; i++){
    	dp[i] = dp[i-1] + dp[i-2];
    }
    
    System.out.println(dp[n]);
}

 

하향식(Top-down)

• 재귀 함수를 이용해서 구현하는 방법
• 시간 복잡도: O(N)

static int[] dp;

public static void main(String[] args){
	dp = new int[n];
    
    System.out.println(fibo(30));
}


public static int fibo(int x){
	if(x == 1 || x == 2){
    	return 1;
    }
    //이미 계산한적 있는 문제면 그대로 반환
    if(dp[x] != 0){
    	return dp[x];
    }
    
    dp[x] = fibo(x-1) + fibo(x-2);
    
    return dp[x];
}

 

26분 51초