다이나믹 프로그래밍(Dynamic Programming)

 다이나믹 프로그래밍은 "한 번 푼 걸 다시 풀어야 하는 문제의 경우 효율적으로 풀 수 있게끔 하는 알고리즘"이다. 문제를 비효율적으로 반복해서 풀다보면, 프로그램 속도가 느려지기도 하고, 말 그대로 정말 비효율적인 코딩이 된다.

 

 대표적인 예시를 들어보자면, 피보나치 수열이 있다. 피보나치 수열은 앞의 두 숫자를 더해서 수가 나열되는 규칙을 지니고 있다. 이 것을 점화식으로 표현하자면, 

이렇게 간단하게 표현할 수 있다.

문제를 이런 식으로 풀다보면, 계속해서 구했던 값인데도 불구하고 비효율적으로 계속해서 다시 구해야되는 일이 발생한다. 5라는 숫자를 넣어서 예를 들자면,

5는 굉장히 작은 축에 속하는 숫자임에도 불구하고, 2를 3번이나 다시 계산해야된다. 더 큰 숫자의 경우에는 더 비효율적이다. 이럴 때에 다이나믹 프로그래밍을 이용하면  굉장히 효율적으로 풀 수 있다.

 

다이나믹 프로그래밍을 쓰려면 두 가지 조건이 충족되어야 한다.

 

<조건>

1. 큰 문제를 작은 문제로 나눠서 풀 수 있다.

2. 작은 문제의 정답이 큰 문제에서의 작은 문제 답과 동일하다.

 

이 조건이 충족되었다면, 다이나믹 프로그래밍을 사용할 수 있다. 다이나믹 프로그래밍에 대해 피보나치를 대입해서 얘기해보자면, 구한 결과 값은 배열에 저장해서 동일한 계산을 여러 번 반복되어 수행되는 것을 방지하여 효율적인 프로그래밍을 구현하면 된다. 아까 5를 계산할 때에는 2를 3번 다시 계산해야 했지만, DP를 이용한다면 1번만 계산하면 된다.(배열에 이미 그 값이 저장되어 있기 때문에 갖다 쓰기만 하면 됨) 이것을 메모이제이션(Memoization)이라고 한다.

 메모이제이션에 대해 짧게 짚고 넘어가자면,

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

즉, 이 기술은 동적 계획법(Dynamic Programming)에서 핵심이 되는 기술이라고 할 수 있다.

 

피보나치 수열을 동적 계획법에 맞게 효율적인 코딩을 한다면 코드는 아래와 같다.

public class DP_fibonacci {
	static int[] data= new int[100];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(fibonacci(5));

	}
	
	private static int fibonacci(int x) {
		if(x<=0) 
			return 0;
		else if(x<2) // 첫 번째와 두 번째 수는 항상 1로 고정되어 있기 때문에..
			return 1;
		if(data[x]!=0) { // 이미 계산 했던 값이 있을 경우
			return data[x];
		}
		else {
			data[x]=fibonacci(x-1)+fibonacci(x-2);
			return data[x];
		}
	}

}