다락방

1003 피보나치 함수 #include using namespace std; int fibo(int num); int check_zero = 0, check_one=0; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int test_case; cin >> test_case; for (int i = 0; i > tmp; fibo(tmp); cout

동적계획법(DP : Dynamic Programming) 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘 중복 계산을 줄여서 계산속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다 일반적으로 재귀로 구현되며 메모이제이션(memoization) 기법을 사용하여 중복 계산을 피한다 메모이제이션 - 이전에 계산된 결과를 저장하고 다음에 동일한 계산에 필요할 때 저장된 결과를 이용하여 중복계산을 피함으로서 성능을 향상 시킬 수 있다. 구현단계 문제를 하위 문제로 쪼갠다 하위 문제를 재귀적으로 해결한다 결과를 저장한다(메모이제이션, 테블레이션) 저장된 결과를 이용해 큰 문제를 해결한다. 동적 계획법 조건 최적부분구조(Optimal Substucture) 전..