로그인

검색

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 게시판 관련

    Date2014.11.01 CategoryTool/etc ByMoA Views15455
    read more
  2. Start Something! - Windows 8 개발 공식 사이트

    Date2012.08.02 CategorySite ByNaya Views3390
    Read More
  3. Windows 10 앱 개발(UWP)

    Date2015.10.13 CategoryAPI/MFC ByMoA Views3383
    Read More
  4. CString class

    Date2013.07.28 CategoryAPI/MFC ByMoA Views3382
    Read More
  5. 스레드 강좌 + CreateThread() 와 _beginthreadex() 함수의 차이

    Date2013.07.28 CategoryAPI/MFC ByMoA Views3378
    Read More
  6. What does set -e mean in a bash script?

    Date2021.04.29 CategoryTool/etc ByOBG Views3368
    Read More
  7. 에디트 플러스, VS 2008 컴파일 환경 설정

    Date2013.07.28 CategoryTool/etc ByMoA Views3365
    Read More
  8. [액션게임 만들기] 10. 캐릭터 기술 구현

    Date2014.05.07 CategoryPython ByMoA Views3364
    Read More
  9. Which Font is the default for MFC Dialog Controls

    Date2013.06.12 CategoryAPI/MFC ByMoA Views3345
    Read More
  10. GetLastInputInfo 함수

    Date2013.12.06 CategoryAPI/MFC ByMoA Views3337
    Read More
  11. MFC에서 생성,사용되는 파일 확장자

    Date2013.08.30 CategoryAPI/MFC ByMoA Views3335
    Read More
  12. Redmine 설치

    Date2013.07.28 CategoryTool/etc ByMoA Views3330
    Read More
  13. Simplified Logger Class

    Date2013.07.28 CategoryC/C++ ByMoA Views3328
    Read More
  14. [액션게임 만들기] 5. 장면 전환

    Date2014.05.07 CategoryPython ByMoA Views3322
    Read More
  15. extern "C" 에 관하여

    Date2013.07.28 CategoryC/C++ ByMoA Views3320
    Read More
  16. 구글 검색 알고리즘의 원리

    Date2012.08.02 CategoryAlgorithm ByNaya Views3313
    Read More
  17. [액션게임 만들기] 6. 게임 화면 출력

    Date2014.05.07 CategoryPython ByMoA Views3310
    Read More
  18. [농장게임 만들기] 4. 펜스를 그리자

    Date2014.04.30 CategoryPython ByMoA Views3307
    Read More
  19. Simple Add-On Wait Dialog in MFC

    Date2013.11.21 CategoryAPI/MFC ByMoA Views3305
    Read More
  20. 큰 수 구하기 알고리즘

    Date2012.08.02 CategoryAlgorithm ByNaya Views3303
    Read More
  21. Numpy의 axis 변경

    Date2023.06.09 CategoryPython ByOBG Views3301
    Read More
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 ... 15 Next
/ 15