Dynamic Programming(동적계획법) 알고리즘

 Dynamic Programming (동적계획법) 이란?

 동적계획법은 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법 입니다. 핵심기술은 memoization 으로 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술입니다.

 

 구현

 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷합니다. 동적 계획법 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산값을 이용해 원래 문제의 답을 산출합니다. 분할정복과의 차이점은 메모이제이션 기술의 사용 여부에 있습니다.

 

구현 방식은 top-down, bottom-up 방식으로 구분됩니다.

top-down 방식

 - 큰 문제를 작은 문제를 호출하는 방식으로 재귀함수를 이용하여 풀어줍니다.

botton-up 방식

 -   가장 작은 문제에서 큰 문제로 답을 찾아가는 방식으로 반복문을 이용하여 풀어줍니다.

 

 예제

 피보나치를 예제로 들겠습니다.

f(5)를 구한다고 가정할 때의 구해야 하는 식입니다.

형광펜 친 곳을 보시다시피 이미 구해져있는 값인데 또 계산을 해야합니다.

그렇다면 이미 구해진 값을 저장한 후 해당 값을 호출하면 프로그램 실행 속도가 훨씬 짧아지겠죠?

이렇게 한 번 계산한 값을 다시 사용해주기 위해 저장하는 기술을 메모이제이션이라고 합니다.

 

top-down 방식

static int top_down(int N) {
	if (N<=2) return 1;
	
	if (dp[N]!=0) return dp[N]; // 이미 값이 있다면 해당 값 리턴
		
	return dp[N] = top_down(N-1)+top_down(N-2);
}

 

bottom-up 방식

static void bottom_up() {
	dp[0] = 0;
	dp[1] = 1;
	for (int i=2;i<=N;i++) {
		dp[i] = dp[i-1]+dp[i-2];
	}
}

 

저는 개인적으로 bottom-up을 자주 쓰는데 dp.. 너무 어렵습니다... 쉬운 문제부터 차근차근 풀어나가면서 감을 익히는게 중요한거 같습니다.