[Algorithm] 다이나믹 프로그래밍

-다이나믹 프로그래밍이란?

  솔직히 여러 블로그나 강의를 봤을 때 드는 예시가 대표적으로 피보나치 수열이라 개념의 이해자체는 쉬웠다. 분할 정복 방식과는 다른 형태로 어떤 큰 문제가 작은 문제로 나눠질 때 또 이 큰 문제가 더 큰 문제의 작은 문제일 때, 동시에 해당 값들에 변화가 없을 때 사용한다고 한다. 즉 피보나치 수열에서 f(3) = f(2) + f(1) 이고, f(4) = f(3) + f(2)이므로 f(3)에서의 f(2)와 f(4)에서의 f(2)는 값이 변하지 않는 중복되는 연산이다. 이러한 중복 연산들을 메모이제이션 기법으로 별도로 기록해두고 (캐시같은 개념) 필요할 때 마다 가져다 사용하면 되는 것이다. 즉, f(3)의 결과를 최초로 실행할 때 저장해 둔 후, f(4)를 구할 때 f(3)을 구하기 위해 아래로 쭉쭉 내려갈 필요없이 메모되어있는 값들을 단순히 가져온다면, 기존의 재귀함수로 구현하는 피보나치 수열의 시간 복잡도O(2^N)에서 O(N)으로 효과적으로 줄일 수 있는 기법이라고 한다.

 

  코드를 통해 확인해보자.

 

public class Dynamic_Programming {
	static long d[] = new long[100]; // 메모이제이션 기법으로 이미 구한 값은 저장해둔다. 그러므로 O(N)의 시간 복잡도를 갖는다.
	public static long dp(int x) { // O(2^N)의 시간 복잡도를 가진다. 굉장히 오래 걸린다.
		if(x==1) return 1; // 피보나치 수열에서 1과 2는 1로 고정되어있다.
		if(x==2) return 1;
		if(d[x] !=0) return d[x]; // 연산을 수행하다 이미 메모되어 있는 값이 있을 경우 반환하고
		return d[x] =dp(x-1) + dp(x-2);  // 메모되어있지 않으면 메모 후 반환한다.
	}
	public static void main(String[] args) {
		System.out.println(dp(50));

	}

}

  솔직히 이 코드만 놓고보면 굉장히 이해가 쉬운데, 이를 어디에 적용해야 할 지에 대한 응용력을 기르는 것이 중요하다고 생각한다. 화이팅~!!