Dynamic Programming은 알고리즘을 공부할 때 필수로 배우는 개념이며, 아마 알고리즘을 처음 접하는 사람들에게 가장 어려운 파트일 것이다. 그러나 한번 이해하고 나면 다른 알고리즘에 비해 상대적으로 쉽게 적용할 수 있는 것이 사실이다. 해당 페이지에서는 컴퓨터 과학 분야에서 매우 유명한 문제들을 예시로 설명하였다.
Brute Froce는 무차별 대입이라고도 하며, 가능한 모든 경우의 수를 계산하는 것이다. 일명 ‘계산 노가다’의 학술적 개념. 이 방법을 문제에 적용할 경우, 정확도 100%를 보장하지만, 시간과 자원이 엄청나게 들어서 매우 비효율적이다.
ex) 체커 게임(체스나 바둑보다 규칙이 훨씬 간단한 보드 게임)을 컴퓨터를 이용한 브루트 포스로 18년 간 계산하여 모든 경우의 수를 분석했다. 분석 결과는 양쪽 모두 최선의 플레이를 하면 무조건 비긴다는 것.
Greedy Algorithm(탐욕 알고리즘)은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 방법이다. 매 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.
Greedy Algorithm이 잘 작동하는 문제는 다음 조건을 만족한다.
이를 만족시키지 못하면 Greedy Algorithm은 최적 해를 구하지 못한다. 하지만 이런 경우에도 Greedy Algorithm은 Approximation Algorithm(근사 알고리즘)으로 사용할 수 있으며, 대부분 계산 속도가 빠르기 때문에 실용적이다.
Dynamic Programming(동적 계획법;DP)은 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 풀고 그 결과를 결합하여 문제를 해결하는 방법이다. 일반적으로 재귀적 솔루션을 공식화한 후 memoization 또는 bottom-up 방식을 통해 DP로 전환한다.