동적 계획법은 큰 문제를 작은 문제로 나눠서 최종 문제를 해결하는 알고리즘이다. 작은 문제를 처리할 때 수행되는 답을 저장해 놓고 다음번에 필요할 때 그 값을 불러와서 처리한다. 재활용 개념이라고 이해하면 쉽다. 분할 정복과 비슷한 개념이지만 분할 정복과 동적 계획법의 차이점은 분할 정복에서의 쪼개진 작은 문제들은 중복되지 않지만 동적 계획법에서 쪼개진 문제는 서로 연관성이 있다는 점이다. (분할 정복에 대해서는 나중에 공부한 후 포스팅 예정입니다.) 개념 동적 계획법은 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘입니다. 피보나치 수열을 재귀로 표현했을 때 결함이 생기는데 이를 동적 계획법으로 보완한 사례를 보면서 알아 보겠습니다. ..
