로그인

검색

Algorithm
2012.08.13 10:07

동적 프로그래밍

조회 수 3238 추천 수 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 15454
118 API/MFC WaitForSingleObject와의 삽질.. MoA 2013.07.28 2965
117 API/MFC Thread Programming Naya 2012.08.02 2961
116 Deeplearning Using Machine Learning to Predict Customers’ Next Purchase Day OBG 2024.02.27 2942
115 Deeplearning 추천(Recommendation) 시스템 - 알고리즘 Trend 정리 OBG 2021.08.03 2941
114 Python 2048 Game in Python OBG 2022.09.22 2937
113 API/MFC VC의 소스 파일, sln파일 관리 MoA 2013.07.28 2921
112 Tool/etc Flash CS5 and Version Control MoA 2013.10.11 2913
111 Library CSpreadSheet MoA 2014.02.03 2911
110 Deeplearning 내 마음대로 선정한 머신러닝/딥러닝 학습 추천 서적 OBG 2023.08.14 2909
109 API/MFC MFC TIP MoA 2013.07.28 2885
108 JAVA/Android 안드로이드 어플 개발 사이트 MoA 2013.03.11 2881
107 JAVA/Android 시스템 분석을 위한 쉘 명령어 MoA 2013.05.28 2865
106 Site 이미지공학(IE) 연구실 MoA 2013.07.28 2854
105 Site 알고리즘 정리된 블로그 MoA 2013.07.28 2850
104 Deeplearning 강화학습 학습 관련 정리 OBG 2022.08.10 2850
103 Python FastAPI 톺아보기 - 부제: python 백엔드 봄은 온다 OBG 2023.01.25 2845
102 Library High-speed Charting Control MoA 2013.07.28 2830
101 API/MFC MFC로 그림 그리기 Naya 2012.08.02 2809
100 API/MFC 세마포어를 이용한 생산/소비자 Naya 2012.08.31 2800
99 Tool/etc AWS 망 분리하기 OBG 2022.09.06 2800
Board Pagination Prev 1 ... 5 6 7 8 9 10 11 12 13 14 15 Next
/ 15