다이나믹 프로그래밍 (Dynamic Programming) 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 기법 1. Overlapping Subproblem - 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. - 문제를 작은 문제로 쪼갤 수 있다. 2. Optimal Substructure - 문제의 정답을 작은 문제의 정답에서 구할 수 있다. - 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. • 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. • Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때 마다 정답이 같다. • 따라서, 정답을 한 번 구했으면, 정답을 어딘가에 메모해놓는다. • 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 ..
