Dynamic Programming (동적 계획법, DP)

Dynamic Programming (동적 계획법)

동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로, 복잡한 문제를 간단한 하위 문제로 나누어 푸는 방법이다.

 

동적 계획법 특징

DP는 메모리를 사용해서 실행 시간을 줄여야 하는 알고리즘으로 이전에 계산한 값을 저장하고 재활용함으로써 중복 계산을 줄이는 특징이 있다. 이 방법은 피보나치 수열 계산뿐만 아니라, 최단 경로, 최장 공통부분 문자열 등 다양한 분야에서 사용된다.

 

동적 계획법 방법

모든 작은 문제들을 한 번만 풀어야 한다. 따라서 정답을 구한 하위 문제의 답은 어딘가에 메모해놓는다. 다시 그 보다 큰 문제를 풀어나갈 때, 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제에 대한 결과값을 이용하는 것이 DP 이다.

즉, 상향식 접근법으로, 가장 작은 부분의 해답을 구한 뒤 이를 저장하고, 저장한 값을 이용하여 상위 문제를 풀어가는 방식이라고 하면 되겠다. 이때 동적계획의 핵심은 Memoization(메모이제이션) 이라는 기법이다.

 

 

부분 반복 문제 (Overlapping Subproblem)

동적계획법의 등장은 피보나치 수열이라고 한다.

 

피보나치 수열(Fibonacci numbers) - 이전 두 항의 합이 다음 항이 되는 수열. 즉, 첫째 항과 둘째 항이 1이고 이후 모든 항은 모든 항은 바로 앞 두항의 합으로 이루어지는 수열을 의미한다.

[1, 1, 2, 3, 5, 8, 13, 21, 34,...]과 같은 형태로 구성된다.

 

public static int Fibonacci(int n) {
	if (n <= 1) {
    	return n;
    } else {
    return Fibonacci (n - 1) + Fibonacci(n - 2);
    }
 }

위와 같이 메모이제이션을 사용하지 않으면 같은 함수를 계속해서 중복 호출을 하기 때문에 재귀함수로 구현을 하면 시간복잡도 O(2^n)을 갖게 된다. 중복되는 호출로 인해 굉장히 좋지 않은 효율을 갖는 것을 볼 수 있다.

 

 

Memoization (메모이제이션)

위의 중복되는 연산과정을 해결하기 위해서는 Memoization(메모이제이션)이라는 동적계획법의 개념이 도입되게 된다.

Memoization(메모이제이션)은 컴퓨터 프로그램이 동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

 

메모제이션 특징

• 같은 문제를 다시 호출 하면 메모했던 결과를 그대로 가져온다 
• 값을 기록해 놓는다는 점에서 캐싱(Cachig)이라고 한다
• DP에만 국한된 개념이 아니다. 한 번 계산된 결과를 담아 놓기만 하고 DP가 아닌 다른 방식으로도 사용될 수 있다. (캐싱,메모이제이션)

피보나치 함수를 예로 들었을 때, 이미 계산된 결과를 저장하면 아래의 색칠된 노드만 계산이 처리되어 프로그램의 작업 처리속도를 크게 향상시킬 수 있다.

// 일반 재귀 함수
// 중복된 계산 반복.
// 시간복잡도 O(2^n)으로 x의 수가 커질수록 복잡도 증가
static int Fibonacci(int x) {
   if( x ==1 || x==2) return 1;
   return Fibonacci(x-1) + Fibonacci(x-2);
}


// Memoization 
// 하위 문제의 결과 값을 dp[]배열에 저장, 필요할 때마다 계산된 값 호출
static int Fibonacci(int x) {
   if( x ==1 || x==2)
   	return 1;
   if(dp[x] != 0)
   	return dp[x];
    
   dp[x] = Fibonacci(x-1) + Fibonacci(x-2);
   
   return dp[x];
}

 

 

Dynamic Programming (동적 계획법) 조건

동적 계획법을 적용하기 위해서는 위 정의에서 본 것처럼, 두 가지 속성을 만족시켜야 한다.

 

1. 최적 부분 구조(Optimal Substructure)

상위 문제를 하위 문제로 나눌 수 있으며 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다.

 

2. 중복되는 부분 문제(Overlapping Subproblem)

동일한 작은 문제를 반복적으로 해결해야 한다.

 

 

DP 구현 방법

DP 구현 방법은 일반적으로 두 가지 방식, Top-down(하향식)과 Bottom-up(상향식)으로 구성된다.

 

Top-down(하향식)

상위 문제를 해결하기 위해서 하위 문제를 재귀적으로 호출하여  하위 문제를 해결함으로써 상위 문제를 해결하는 방식이다. 이 때 해결해놓은 하위 문제를 저장해 놓기 위해 Memoization이 사용된다.

 

피보나치 함수를 만들 때 Top-down은 재귀 호출을 사용하여 구현한다

public class Topdown {
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		System.out.println(Fibonacci(n));
		
	}
	
    // Top-down
	static int Fibonacci(int x) {
    
		if( x ==1 || x==2)
        	return 1;
		if(dp[x] != 0)
        	return dp[x];
            
		dp[x] = Fibonacci(x-1) + Fibonacci(x-2);
        
		return dp[x];
	}
}

 

Bottom-up(상향식)

하위에서부터 문제를 해결해나가면서 먼저 계산했던 문제들의 값을 활용해서 상위 문제를 해결해나가는 방식으로 DP의 전형적인 형태는 Bottom-up이다. 여기서 사용되는 문제 결과 값 저장용 리스트는 DP 테이블이라고 부른다.

 

Bottom-up 방식은 반복문을 사용해서 구현한다.

public class Bottomup {

	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		
		System.out.println(Fibonacci(n));
	}
	
    // Bottom-up
	static int Fibonacci(int x) {
    
		dp[1] =1;
		dp[2] =1;
        
		for(int i=3; i<x+1; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
        
		return dp[x];
	}
}

 

재귀함수는 구현이 쉽고 이해하기 쉽지만 시간 복잡도가 높아 큰 수를 계산하기 어려우며

동적 계획법은 이미 계산한 값을 활용하여 계산 시간을 줄일 수 있지만 메모리 사용량이 높아질 수 있다.