tabulation1 [백준 24416/c++]피보나치 수 1 어제랑 다른 버전의 피보나치 수 문제이다 재귀와 다이나믹 프로그래밍의 차이를 알 수 있는 문제였다 재귀는 반드시 함수를 만들어서 풀어야 하며, 매번 연산을 하면 너무 느리므로 top-down 방식의 memoization 을 사용하여 연산 속도를 향상 시킬 수 있다 (memoization이 필수는 아님) 다이나믹 프로그래밍의 경우 반드시 함수를 만들 필요는 없고 배열과 반복문만으로 만들 수 있으며 bottom-up 방식의 tabulation 을 사용한다 (tabulation이 필수임) 일반적으로 다이나믹 프로그래밍이 재귀함수를 사용한것보다 시간복잡도, 공간복잡도가 낮아서 성능이 좋다 https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 .. 2022. 7. 18. 이전 1 다음