동적 프로그래밍
-
동적 프로그래밍 개념프로그래밍 기초/알고리즘 2022. 1. 12. 10:45
동적 프로그래밍 동적 프로그래밍 개념 큰 문제의 해답에 작은 문제의 해답이 포함되는 알고리즘을 재귀적으로 처리할 때 나타나는 비효율을 제거하기 위한 프로그래밍 방식을 동적 프로그래밍이라고 한다. 가령 피보나치수열의 경우 다음과 같은 식으로 나타난다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 이를 재귀적으로 해결하기 위해서는 기존에 구했던 해답을 다시 구하는 등의 반복이 일어난다. 이러한 문제를 해결하기 위해 부분 결과를 저장하면서 해를 구하는 것이 동적 프로그래밍의 핵심이다. 가령 위에서 설명한 피보나치수열의 문제를 동적 프로그래밍을 적용해 해결한다면 다음과 같이 풀 수 있다. 피보나치수열 알고리즘 fib(n) { if (f[n] ≠ 0) then return f[n]; el..