[알고리즘] 동적 계획법, 메모이제이션이란?

동적 계획법 중 메모이제이션을 적용하는 문제들이 참 많았는데, 무슨 소리인지 제대로 이해하지 못했다. 그래서 오늘 각잡고 조사해보았다. ^_^ 1. 동적 계획법이란? 동적 계획법 (dynamic programming): 처음 주어진 문제들을 분할하고, 이로부터 본 문제에 관한 답을 도출하는 접근 방법이다. 특히 부분 문제들의 수가 기하급수적으로 증가할 때 유용하다. 동적 계획법은 여러 문제 해결에 사용되는 부분 문제에 대한 결과를 여러번 계산하는 대신, 한 번만 계산하고 이를 재활용하여 속도를 향상시킨다는 점에서 분할 정복법과 차이가 있다. 이를 위하여 각 문제의 답을 메모리에 저장해야 하는데, 이미 계산된 값을 저장해두는 메모리의 장소를 캐시(cache)라고 하며, 두 번 이상 계산되는 부분 문제를 중..

2021.11.27