동적 계획법(Dynamic Programing, Dp)

동적 계획법 - 위키백과, 우리 모두의 백과사전

동적 계획법

동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 

 

많은 알고리즘 문제를 풀다보면 구했던 값을 불필요하게 계속 구하는 과정을 할 때가 있다. 다음 예시를 보자

 

예시

피보나치 수열을 만들어보자

int fib(int n) {
		if(n == 0) return 0;
		else if (n==1)return 1;
		else return fib(n-1) + fib(n-2);
}

 

만약 5번째 수열을 구하면 함수가 어떻게 실행될까?

f(3)을 두번 구하게 된다. 수가 커지면 커질수록 불필요한작업을 더 많이 하게 된다.

 

메모이제이션 - 위키백과, 우리 모두의 백과사전

메모이제이션

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

불필요한 계산을 없애기 위하여 계산한 값을 메모리에 저장하여 반복되는 수행을 안하게 된다.

 

위예시를 메모이제이션을 사용하여 변경하자

 

변경된 예시

int fib(int n,int []arr) {
		if(n == 0) return 0;
		else if (n==1)return 1;
		else {
			if(arr[n]==0)
				arr[n]=fib(n-1,arr)+fib(n-2,arr);
			return arr[n];
		}

배열 arr의 저장되있는가를 확인하여 없으면 계산을 하고 있으면 값을 반환해준다.

불

 

 

Top-down&Bottom-up

동적 계획법에는 두가지의 구현방식이 있다.

 

Top-down :큰 문제를 조깨가며 푼다.

Bottom-up: 작은 문제를 합해가며 푼다.

 

Top-down은 위의 예시와 같이 재귀적으로 5를 구하기 위해 4와 3을 호출하고 3을 구하기 위해 2와 1의 값을 호출하는 

것처럼 큰값에서 작은값을 향한다.

 

Bottom-up 예시

int fib(int n,int[] arr)
{
  arr[0] = 0;
  arr[1] = 1;
  for (int i=2; i<=n; i++)
    arr[i] = arr[i - 1] + arr[i - 2];
  return arr[n];
}

위의 예시처럼  1과 2를 더하여 3을 구하고 3과 4를 더하여 5를 구하는 방식이다.