동적 프로그래밍

Naya

조회 수 1197 추천 수 0 댓글 0

단축키

Prev이전 문서

Next다음 문서

가 크게 작게 위로 아래로 게시글 수정 내역 댓글로 가기 인쇄

단축키

Prev이전 문서

Next다음 문서

가 크게 작게 위로 아래로 게시글 수정 내역 댓글로 가기 인쇄

1. 팩토리얼 계산하는 문제

분할 정복

int factorial(int n)
{
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;
}

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);
}

동적 프로그래밍

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;
}
}

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);
}

동적 프로그래밍

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];
}

동적 프로그래밍으로 하는 경우 중복하여 계산하게 되는 경우를 막을 수 있으므로 계산시간이 더 빠르다.