DynamicProgramming(DP)-알고리즘08

1. 개요 DP(동적 계획법)은 큰 문제를 작은 부분문제들로 나누어서 푸는 하나의 문제해결 패러다임이다. 작은 문제들의 결과를 저장했다가 큰 문제를 풀때 재활용한다. 2. 목적 DP를 사용하는 이유는 일반적인 재귀는 동일한 작은 문제들을 반복해서 계산하기 때문에 비효율인 계산으로 시간이 오래걸리기 때문이다. ex) 피보나치 수열 피보나치 수열은 다음과 같다 1 1 2 3 5 8 13 21 34 55... 이를 재귀함수로 나타내면 f(n) = f(n-1) + f(n-2) 이다. f(5)를 재귀트리로 나타내면 아래와 같다. 이때 f(3)에서 f(2)를 계산했으나 f(4)에서 f(2)를 또 구해야 한다. 이러한 이유로 계산수가 기하급수적으로 늘어나게 되는데 이런 문제점을 저장했다가 다시 사용하는 방식으로 DP..

2023.08.20