로그인

검색

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
238 LLM 만능 프롬프트 OBG 2024.04.07 2593
237 LLM [VESSL AI] 뉴욕주민의 프로젝트플루토 — LLM, LLMOps를 활용한 금융 미디어의 혁신 OBG 2024.04.21 2599
236 Tool/etc HuggingFace 공동창업자가 추천하는 AI 분야 입문 서적 OBG 2024.05.24 2606
235 Tool/etc 2016년에 자바스크립트를 배우는 기분 MoA 2016.12.27 2612
234 Graphic Direct3D 9 compile MoA 2013.07.28 2614
233 LLM The difference between quantization methods for the same bits OBG 2024.04.14 2615
232 API/MFC InvalidateRect 함수, flag성 메세지 MoA 2013.07.25 2616
231 API/MFC #pragma MoA 2013.07.28 2618
230 Tool/etc 에디트 플러스, VS 2008 컴파일 환경 설정 너울 2012.04.02 2619
229 서버 SSH-Tunneling을 통한 MySQL 서버 연결 OBG 2023.04.21 2621
228 Library pthread MoA 2013.07.28 2627
227 API/MFC UpdateWindow 함수에 대하여.. MoA 2013.07.25 2640
226 API/MFC 태스크 대화상자 (Task Dialog) MoA 2013.10.22 2642
225 Deeplearning RuntimeError: CUDA error: CUBLAS_STATUS_ALLOC_FAILED ... OBG 2022.09.06 2644
224 Deeplearning LLaMA: INT8 edition OBG 2023.03.09 2645
223 API/MFC 모달창 세팅값 저장 MoA 2013.07.28 2648
222 Deeplearning [한빛미디어] 머신러닝·딥러닝 도서 선택 가이드 OBG 2023.06.11 2651
221 JAVA/Android 안드로이드 개발 참고 사이트 MoA 2013.03.31 2662
220 Tool/etc How To Set Up Multi-Factor Authentication for SSH on Ubuntu 20.04 OBG 2023.01.17 2664
219 API/MFC Legacy MFC 어플리케이션을 MFC feature pack으로 포팅 MoA 2013.07.30 2672
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 ... 15 Next
/ 15