로그인

검색

Algorithm
2012.08.13 10:07

동적 프로그래밍

조회 수 4107 추천 수 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 20938
282 LLM [VESSL AI] 뉴욕주민의 프로젝트플루토 — LLM, LLMOps를 활용한 금융 미디어의 혁신 OBG 2024.04.21 3588
281 LLM PEFT: Parameter-Efficient Fine-Tuning of Billion-Scale Models on Low-Resource Hardware OBG 2024.04.15 2796
280 LLM The difference between quantization methods for the same bits OBG 2024.04.14 3713
279 LLM Mixture of Experts - Part 2 OBG 2024.04.14 2995
278 LLM ChatGPT의 강력한 경쟁 언어모델 등장!, Mixtral 8x7B OBG 2024.04.14 3446
277 LLM Real-Time Stock News Sentiment Prediction with Python OBG 2024.04.11 3364
276 LLM Getting Started with Sentiment Analysis using Python OBG 2024.04.11 3510
275 LLM How LLMs Work ? Explained in 9 Steps — Transformer Architecture OBG 2024.04.11 3409
274 LLM 만능 프롬프트 OBG 2024.04.07 3644
273 LLM A Beginner's Guide to Prompt Engineering with GitHub Copilot OBG 2024.04.04 2957
272 LLM [12월 1주] 떠오르는 '미스트랄 7B'...'라마 2' 이어 한국어 모델 세대교체 주도 OBG 2024.03.05 5683
271 Deeplearning Using Machine Learning to Predict Customers’ Next Purchase Day OBG 2024.02.27 4116
270 서버 멀티-플레이어 게임 서버와 레이턴시 보상 테크닉 OBG 2024.01.16 2726
269 Deeplearning [ifkakao] 추천 시스템: 맥락과 취향 사이 줄타 OBG 2024.01.10 3090
268 Tool/etc How to stop programmers to copy the code from GitHub when they leave the company? OBG 2024.01.02 3608
267 Site 10 Useful/Fun/Weird Github Repos You Have to Play Around With OBG 2023.12.28 3665
266 Site 모든 개발자를위한 10 가지 특별한 GitHub 리포지토리 OBG 2023.12.28 3272
265 Deeplearning 마이크로소프트가 공개한 무료 AI 코스들 OBG 2023.11.28 3589
264 Deeplearning 내 마음대로 선정한 머신러닝/딥러닝 학습 추천 서적 OBG 2023.08.14 4039
263 Deeplearning LSTM-AE를 이용한 시퀀스 데이터 이상 탐지 OBG 2023.08.14 3558
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 ... 17 Next
/ 17