로그인

검색

Algorithm
2012.08.13 10:07

동적 프로그래밍

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


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


?

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
공지 Tool/etc Programming 게시판 관련 2 MoA 2014.11.01 11502
258 Site 프로그래밍 관련 사이트 MoA 2012.08.02 1908
257 STL/Boost boost::shared_ptr 소개 Naya 2012.08.02 1982
256 API/MFC 윈도우 프로그램의 종료 메시지 순서 Naya 2012.08.03 2668
» Algorithm 동적 프로그래밍 Naya 2012.08.13 2583
254 API/MFC stdafx.h 사용 (미리 컴파일된 헤더) Naya 2012.08.13 3244
253 API/MFC 세마포어를 이용한 생산/소비자 Naya 2012.08.31 2471
252 Site IT 세미나 유튜브 동영상 Naya 2012.09.10 2174
251 Site 윈도우 8 앱 개발 동영상 강의 Naya 2012.09.10 2199
250 C/C++ 코드 실행 시간 계산 Naya 2012.09.27 2300
249 Library [OpenCV] 얼굴 인식 예제 file MoA 2012.10.14 3336
248 Reversing Dumpbin.exe 사용 Naya 2012.10.21 2046
247 Site 특정 자료형의 데이터를 binary(hex값, 2진수값)으로 변환 Naya 2012.11.15 2970
246 Site Base64 decoder (binary file로 저장) Naya 2012.11.15 2428
245 C/C++ C++에서 base64로 인코딩 Naya 2012.11.15 2994
244 Site Great summary cheat sheet (OpenCV) MoA 2013.01.04 2652
243 Tool/etc Visual Studio Debug Tips MoA 2013.02.19 2723
242 JAVA/Android 이클립스에서 ADT 설치시 에러 해결 MoA 2013.03.09 2475
241 JAVA/Android 안드로이드 어플 개발 사이트 MoA 2013.03.11 2364
240 JAVA/Android 안드로이드 개발 참고 사이트 MoA 2013.03.31 2019
239 JAVA/Android 안드로이드 프로세스 확인 MoA 2013.04.09 2208
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 ... 15 Next
/ 15

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

나눔글꼴 설치 안내


이 PC에는 나눔글꼴이 설치되어 있지 않습니다.

이 사이트를 나눔글꼴로 보기 위해서는
나눔글꼴을 설치해야 합니다.

나눔고딕 사이트로 가기

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5