로그인

검색

Algorithm
2012.08.13 10:07

동적 프로그래밍

조회 수 3240 추천 수 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 15455
258 LLM How LLMs Work ? Explained in 9 Steps — Transformer Architecture OBG 2024.04.11 2459
257 Web Address Bar Install for Progressive Web Apps on the Desktop OBG 2021.12.15 2462
256 Deeplearning Keras를 활용한 주식 가격 예측 OBG 2022.09.02 2463
255 Graphic DirectX 9.0c SDK을 Visual Studio2008에 적용방법 MoA 2013.07.28 2471
254 Database 수신 기한이 지난 데이터를 MySQL에서 삭제할 때의 이야기 OBG 2023.01.25 2474
253 Site 개발에 도움되는 사이트 (초보 개발자 꿀팁) OBG 2023.01.28 2491
252 Deeplearning 파이썬 머신러닝 무료 강의 (7시간) OBG 2022.07.06 2492
251 LLM Comparing Replit and Cursor for AI-Powered Coding OBG 2024.09.21 2495
250 Deeplearning 마이크로소프트가 공개한 무료 AI 코스들 OBG 2023.11.28 2504
249 LLM ChatGPT의 강력한 경쟁 언어모델 등장!, Mixtral 8x7B OBG 2024.04.14 2517
248 Deeplearning Reinforcement Learning for Dynamic Pricing Suggestion OBG 2023.04.01 2526
247 Site 모든 개발자를위한 10 가지 특별한 GitHub 리포지토리 OBG 2023.12.28 2531
246 서버 Building Pitaya, Wildlife’s own scalable game server framework OBG 2022.06.07 2546
245 Deeplearning The State of AI & Art 2022 1 OBG 2022.10.06 2548
244 LLM LLM 출력 속도 24배 높여주는 라이브러리 등장했다 OBG 2023.06.30 2552
243 C/C++ 파일 입출력 MoA 2013.07.28 2559
242 Deeplearning Play Super Mario Bros with a Double Deep Q-Network OBG 2022.09.15 2583
241 Site 영상 처리 관련 블로그 MoA 2013.09.29 2584
240 C/C++ C언어의 변수 float와 double - Float Point 처리 MoA 2013.07.28 2585
239 Reversing Dumpbin.exe 사용 Naya 2012.10.21 2587
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 ... 15 Next
/ 15