DP

12장 동적 프로그래밍

11장에서는 재귀적으로 작성하는 법과 재귀로 보다 복잡한 문제를 해결하는 법을 배웠다. 그러나 재귀로 어떤 문제를 해결할 수는 있어도 제대로 사용하지 않으면 또 다른 문제가 발생하기도 한다. 재귀를 잘못 사용할 경우 알고리즘의 시간 복잡도가 O(2^N)과 같은 가장 느린 빅 오 카테고리에 속하게 될 수 있다. 12장에서는 재귀의 속도를 느리게 만드는 가장 흔한 걸림돌을 찾고 그러한 알고리즘을 빅 오 관점에서 어떻게 나타내는지, 어떻게 개선하는지를 배운다. 1. 불필요한 재귀 호출 동일한 하위 문제의 계산 결과를 여러 번 호출하는데, 동일한 인자를 넣었을 때 항상 동일한 결과가 나올 때 2. 빅 오를 위한 작은 개선 이러한 추가적인 재귀 호출을 전부 없앨 수 있는 방법이 있다. 코드에서 결과를 변수에 저장..