DP(동적 계획법) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것. 재귀와 비슷하지만, 재귀와 다른 점은 작은 문제들을 여러번 반복하지 않아 비효율적인 계산을 하지 않아도 된다는 것이다. DP의 사용 조건 1. Overlapping Subproblems(겹치는 부분적인 문제) DP는 기본적으로 문제를 나누고 그 작은 문제들의 결과값을 재활용한다. 즉 동일한 작은 문제로 나눌 수 있어야 한다. ex) 피보나치 수열 —> f(n) = f(n - 1) + f(n - 2) 2. Optimal Substructure(최적 부분 구조) 부분 문제의 최적 결과값을 이용해 전체 문제의 최적 결과값을 구할 수 있어야 한다. 위 그림에서 A → X의 최단경로는..
