동적계획법

 동적 계획법은 문제를 분할하고 부분 문제의 해를 구한 뒤 구해야 할 해를 부분 문제의 해를 이용해서 구하는 방법이다. 이 때 부분 문제의 해는 배열에 기억시켜 놓은 뒤에 재활용한다. 분할 정복과 비슷하다고 생각할지 모르겠다.

아래의 글을 보고 둘 사이의 차이점을 이해해 보자.

 

▶분할 정복법과 동적 계획법을 이용한 n!구하기

1) 분할정복법

int fact(int n);
main()
{
	int n, k;
	table[1] = 1;
	scanf("%d", &n);
	k = fact(n);
}

int fact(int n)
{
	int i;
	if(n < 1) return 1;
	k = n * fact(n-1);
	return k;
} 

2) 동적계획법

void fact(int n);
main()
{
	int n;
	table[1] = 1;
	scanf("%d", &n);
	fact(n);
}

void fact(int n)
{
	int i;

	for(i=2; i <=n;  i++)
        	table[i] = i * table[i-1];
} 

 

 

              <동적계획법>

위의 펙토리얼 프로그램은 n!의 값을 분할정복법과 동적계획법의 과정을 나타낸다.동적 계획법을 이용한 프로그램은 최종 결과값을 만들기 위해 처음부터 하나씩 해결해서 배열에 넣는다. 그렇게 구한 값을 이용하여 최종 결과값을 얻게 된다. 

 

          <분할정복법>

 반면, 분할정복법으로 짜여진 프로그램은 값을 구하기 위해 부분 문제의 해를 구하고, 그 부분문제의 해를 구하기 위해 부분 문제의 부분 문제의 해를 구하는 방식으로 동작한다.

void table[100];
main()
{
	table[0] = 1;
	table[1] = 1;
	scanf("%d", &n);
	fi(n);
}

void fi(int n)
{
	int i;
	for(i=2; i<=n; i++)
        	table[i]:=table[i-1]+table[i-2];
}

 

피보나치 수열을 구하기 위한 점화식은 F(n) = F(n-1) + F(n-2) 이다. 배열을 이용하여 F(1) + F(2), F(2) + F(3), ..., F(n-1) + F(n-2)를 구하는 방식으로 값을 구하였다. 분할 정복법에서는 F(n) = F(n-1) + F(n-2)에서 시작하여 F(n-1)과 F(n-2)를 각각 구한뒤 마지막에 결과를 합치는 방식으로 문제를 푼다.

 

▶ 분할정복법 : 큰 문제를 부분으로 분할하여 각각의 부분 문제를 해결한뒤 결과를 모음

▶ 동적계획법 : 작은 문제를 하나하나 계산하여 원하는 결과에 도달