Ref : Introduction to ALGORITHMS, Third Edition, Thomas H. CormenRef : C++ DS and ALgoriithm Design Principles, Jon carry.※ 해당 게시글을 이해하기 위해서는 자료구조에 대한 기초적인 지식과 적당한 Python/CPP 능력이 필요합니다.쨋든 DP의 기법들인 Memoization/Tabulation을 알아봅시다. (참고로 Memorization이랑 헷갈리시면 곤란합니다.) 메모이제이션은 대게 하향식 방식에서 부분문제의 답을 캐시에 넣어 사용할때를 말합니다. 대게 재귀를 쓰고, 필요한 값만 요청될 때 계산합니다. 또한 다음 조건을 만족할때 성립하게 됩니다.부분 문제 해법을 캐시에 인덱싱하여 저장하는 방법이 유용해야..

Ref : Introduction to ALGORITHMS, Third Edition, Thomas H. Cormen※ 해당 게시글을 이해하기 위해서는 자료구조에 대한 기초적인 지식과 적당한 Python/CPP 능력이 필요합니다.Dynamic Programming(이하 통칭 DP라 함)은 분할 정복 마냥 문제를 나눠서 푸는게 핵심입니다. 단지 분할 정복이랑 다른 점이 있다면 - 나눈 문제들이 답을 서로 공유한다는 점이죠. 그러니까 대충 정리하자면.... DP는 Sub-Problem을 한번 풀과 결과를 데이터 테이블에 저장해 놓습니다.결과적으로 해당 Sub-Problem을 다시 만났을 때 - 계산을 다시 할 필요가 없어집니다.call fib(6) └─ fib(5) └─ fib(4) ..