1. 팩토리얼 계산하는 문제
분할 정복
int factorial(int n)
{
if(n==1) return 1;
else return n*factorial(n-1);
}
{
if(n==1) return 1;
else return n*factorial(n-1);
}
동적 프로그래밍
int factorial(int n)
{
int i;
int product = 1;
for(i=1;i<=n;i++) product *= i;
return product;
}
{
int i;
int product = 1;
for(i=1;i<=n;i++) product *= i;
return product;
}
2. 피보나치 수열 구하는 문제
f(n) = f(n-1) + f(n-2) 인 규칙을 가지는 피보나치 수열 계산
분할 정복
int fibonacci(int n)
{
if(n==1 || n==2) return 1;
else return fibonacci(n-1) + fibonacci(n-2);
}
{
if(n==1 || n==2) return 1;
else return fibonacci(n-1) + fibonacci(n-2);
}
동적 프로그래밍
int fibonacci(int n)
{
int i,series;
int last1 = 1;
int last2 = 1;
if(n==1 || n==2) return 1;
else
{
for(i=2; i<n; i++)
{
series = last1 + last2;
last1 = last2;
last2 = series;
}
return sereis;
}
}
{
int i,series;
int last1 = 1;
int last2 = 1;
if(n==1 || n==2) return 1;
else
{
for(i=2; i<n; i++)
{
series = last1 + last2;
last1 = last2;
last2 = series;
}
return sereis;
}
}
3. 이항 계수 구하는 문제
nCr = n-1Cr-1 + n-1Cr 공식 이용하여 이항 계수 계산
분할 정복
int bincoeff(int n, int k)
{
if(k==0 || k==n) return 1;
else return bincoeff(n-1, k-1) + bincoeff(n-1, k);
}
{
if(k==0 || k==n) return 1;
else return bincoeff(n-1, k-1) + bincoeff(n-1, k);
}
동적 프로그래밍
int bincoeff(int n, int k)
{
int i,j;
int B[0...n][0...n];
for(i=0; i<n; i++)
for(j=0; j<min(i,k); j++)
if(j==0 || j==i) B[i][j] = 1;
else B[i][j] = B[i-1][j-1] + B[i-1][j];
}
{
int i,j;
int B[0...n][0...n];
for(i=0; i<n; i++)
for(j=0; j<min(i,k); j++)
if(j==0 || j==i) B[i][j] = 1;
else B[i][j] = B[i-1][j-1] + B[i-1][j];
}
동적 프로그래밍으로 하는 경우 중복하여 계산하게 되는 경우를 막을 수 있으므로 계산시간이 더 빠르다.
손님