동전개수
-
[알고리즘] Dynamic Programming (동적프로그래밍)SW/Algorithm 2018. 1. 5. 22:00
Dynamic Programming (동적계획법) 분할정복비법처럼 작은 문제들로 나누어 각각 해답을 찾고 원래 문제의 해답을 계산 하지만 중복이 발생하여 반복연산이 많아 수행시간이 길다. => 메모리제이션으로 해결(반복연산 제거) ex) 최적화 문제(최대,최소) : working backward기법 사용 (top-down 방법으로)-> 재귀식으로 정의 (중복계산발생)-> bottom-up 방식 -> 저장할 테이블을 생성 [앞 1~3번째 까지는 최적값을 계산하는 과정이고, 마지막은 최적해답을 계산하는 단계]factorial //많은 중복연산을 함. n=100int f(int n) //메모리제이션 - 미리저장{int i ,f[100];f[0]=1; //base casefor(i=1;i c(n) = c(n-1..