로그인

검색

Algorithm
2012.08.13 10:07

동적 프로그래밍

조회 수 1181 추천 수 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 5307
288 API/MFC __cdecl , __pascal, __stdcall MoA 2013.07.28 1268
287 C/C++ __FILE__ __LINE__ __FUNCTION__ 등 매크로 MoA 2014.01.02 1502
286 LLM [12월 1주] 떠오르는 '미스트랄 7B'...'라마 2' 이어 한국어 모델 세대교체 주도 OBG 2024.03.05 471
285 Python [GUI] Tkinter, wxPython MoA 2013.11.27 1541
284 Python [GUI] wxPython 기본 프로그램 file MoA 2013.11.30 1411
283 Python [GUI] wxPython에서 에러메시지 콘솔로 보는 법 MoA 2013.12.03 1325
282 Deeplearning [ifkakao] 추천 시스템: 맥락과 취향 사이 줄타 OBG 2024.01.10 376
281 Web [Javascript] 비동기, Promise, async, await 확실하게 이해하기 OBG 2022.05.27 396
280 Library [OpenCV] 얼굴 인식 예제 file MoA 2012.10.14 1857
279 Tool/etc [S/W 공학] 월-인원(man-month), LOC MoA 2013.09.23 1355
278 LLM [VESSL AI] 뉴욕주민의 프로젝트플루토 — LLM, LLMOps를 활용한 금융 미디어의 혁신 OBG 2024.04.21 706
277 Python [게임 만들기] 강좌 진행 예정 2 MoA 2014.04.26 2092
276 Python [농장게임 만들기] 1. Nubcake Farms 게임 소개 4 file OBG 2014.04.26 2310
275 Python [농장게임 만들기] 10. 상점을 추가하자 file MoA 2014.05.01 2986
274 Python [농장게임 만들기] 2. Nubcake Farms 클래스 분석 3 file OBG 2014.04.26 1397
273 Python [농장게임 만들기] 3. 배경을 그리자 6 file MoA 2014.04.28 2749
272 Python [농장게임 만들기] 4. 펜스를 그리자 5 file MoA 2014.04.30 1317
271 Python [농장게임 만들기] 5. 플레이어를 추가하자 1 file MoA 2014.04.30 1216
270 Python [농장게임 만들기] 6. 나머지 오브젝트를 그리자 1 file MoA 2014.05.01 1591
269 Python [농장게임 만들기] 7. 농부 행동 추가 1 file MoA 2014.05.01 1216
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 ... 15 Next
/ 15