𝘚𝘭𝘰𝘸 𝘣𝘶𝘵 𝘴𝘵𝘦𝘢𝘥𝘺

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다. 1. 동적 계획법 ; dynamic programming 1.1 개념 분할 정복 패러다임 개념을 확장한 것으로, 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말이다. 언뜻 문제를 보면 비슷하다 생각될 수 있지만, 분할 정복과 구분되는 동적 계획법만의 특성은 다음과 같다. 1. 중복되는 부분 문제(overlapping subproblem) 2. 최적 부분 구조(optimal substructure) 다음과 같은 속성을 만족해야 동적 계획법을 통해 문제를 해결할 수 있다. 전체 문제가 독립적인 부분 문제로 나뉘는 분할 정복 문제와 달리 동적 계획법에서는 중복되는 부분 문제가 반복적으로 등장한다. 또한 최적 부분 구..