로그인

검색

Algorithm
2012.08.13 10:07

동적 프로그래밍

조회 수 3241 추천 수 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];
}


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


?

  1. Programming 게시판 관련

  2. 모달리스 대화상자

  3. [첫게임 만들기] 8. Win or Lose

  4. 리스트뷰에 체크박스 추가 예제

  5. [S/W 공학] 월-인원(man-month), LOC

  6. fwrite(), fread()

  7. 추천 시스템

  8. 정적 배열과 STL vector 속도 비교

  9. CSS, 자바스크립트 강좌

  10. Deploying a Visual C++ Application (배포 방법)

  11. 동적 프로그래밍

  12. ChartFX 7.0 MFC에서 사용하기

  13. Property Sheet의 버튼 속성 변경하기

  14. [농장게임 만들기] 5. 플레이어를 추가하자

  15. 작업자 스레드(Worker Thread) 와 사용자 인터페이스 스레드(User Interface Thread)

  16. Quake 3 source code and review

  17. Stable Diffusion

  18. [액션게임 만들기] 4. 캐릭터 선택 화면

  19. 잡담) AWS에 서버 띄워 놓으니 벼라별 리퀘스트가 다 날아 오네요

  20. Numpy의 axis 변경

  21. 큰 수 구하기 알고리즘

Board Pagination Prev 1 ... 4 5 6 7 8 9 10 11 12 13 ... 15 Next
/ 15