Deeper Learning

Dynamic Programming (동적 계획법) DP는 하나의 문제를 여러 개의 작은 하위 문제로 나누어 풀고 이를 결합하여 최종적인 문제에 도달하는 것이다. 각 하위 문제의 결과를 계산하고 기록하여 같은 하위 문제가 등장하였을 경우 기록된 결과를 사용하여 간단하게 문제를 해결할 수 있다. 위 방법을 통하여 계산량을 줄일 수 있으며 이는 하위 문제가 기하급수적으로 많은 경우 유용하다. Top-down: 큰 문제를 작은 문제로 나누고 재귀호출을 통해 해결한다. Bottom-up: 작은 문제부터 최적해를 쌓아가면서 마지막 궁극적인 최적해에 도달한다. (for loop) Greedy Algorithm DP는 항상 최적해를 구해내지만 모든 경우를 고려한다는 단점이 있다. 그리디 알고리즘은 현 상황에서 최적의..