목록다이나믹 프로그래밍 (1)

hyeonzzz's Tech Blog

[이코테] 8. 다이나믹 프로그래밍

다이나믹 프로그래밍 (동적 계획법) : 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 피보나치 수열 재귀 함수로 구현 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) print(fibo(4)) 문제점 : f(n) 함수에서 n이 커질수록 수행 시간이 기하급수적으로 늘어난다 시간 복잡도 : O(2^N) 동일한 함수가 반복적으로 호출된다. f(n)에서 n이 커질수록 반복해서 호출하는 수가 많아진다. 다이나믹 프로그래밍 조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션 기법(캐싱)으로 구현 (탑다운 방식) # 한 번 계산된 결..
Algorithm 2024. 2. 23. 13:44
이전 Prev 1 Next 다음