동적 계획법이란? 동적계획법은 Dynamic Programming, DP라고도 불린다. 동적계획법은 하나의 문제를 "단 한번만" 푸는 문제이다. 분할정복과 비슷한 성격을 띄고있다. 단 다른 점이라면, 분할정복같은 경우에는 동일한 문제를 여러번 푼다는 점에 있어서 동적계획법과 차이가 있다. 동적계획법을 사용하는데에 있어 아래 두가지 조건을 만족해야한다. 큰 문제를 작은 문제로 나눌 수 있어야 한다 작은 문제에서 구한 정답이 큰 문제에서도 동일한 정답으로 적용해야한다. 동적계획법은 메모이제이션(Memoization)기법을 사용하면서 값을 구하게 된다. 메모이제이션이란, 이미 구한 답을 잠시 배열에 기록해두고, 나중에 동일한 연산을 할 때 사용한다는 기법이다. 분할정복에서의 비효율성 분할정복법의 비효율성은 대..
