OSgood의 개발일기

이번 포스팅에서는 Dynamic Programming의 개념적인 내용을 살펴보겠다. 자세한 적용 예는 좀 더 공부한 후에 더 자세히 포스팅하도록 하겠다. Dynamic Programming는 간단히 말해 부분 문제의 해를 결합해 문제를 해결하는 것을 의미한다. 부분 문제가 서로 중복될 때,즉 부분 문제가 다시 자기 자신의 부분 문제를 공유할 때 적용할 수 있다. 부분문제를 푸는 것은 분할정복 기법(재귀방법)과 비슷하지만 다른 점이 있다. 분할 정복 기법 VS Dynamic Programming 분할 정복 기법(재귀적 방법) Dynamic Programming 부분 문제를 단순히 반복적으로 계산하여서 해결한다. 필요 이상의 계산이 필요하기 때문에 시간이 오래걸릴 수 있다. 부분 문제를 해결한다는 점은 분할..