dp1 🏃[백준/python] DP 유형 모음집 및 접근 컨셉 분할정복 vs 다이나믹 프로그래밍 여러 하위 문제로 나누어 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 해결하는 기법 분할정복다이나믹 프로그래밍 (이하 DP)하위 문제중복이 없음중복 있음즉, 단순 분할정복 수행 시 중복된 작업을 수행(해결 방법은 아래 이어서)고려사항 시간 - 메모리 간의 trade-off DP 구현방법TODO 두 방식의 차이점 체감하기 Top DownBottom Up구현 방법재귀, memoizationfor 루프, Tabulation [생각해보기] 시간복잡도 (피보나치 수열 vs 팩토리얼 문제) 피보나치 수열팩토리얼점화식fibo(n) = fibo(n-1) + fibo(n-2)factorial(n) = n*factorial(n-1)시간복잡도[재귀로 구현 시] O(2^n)함수를 계.. 2024. 8. 28. 이전 1 다음
