동적 계획법(Dynamic Programming)이란?

동적 계획법은 복잡한 문제를 작은 부분 문제로 나누고, 각 부분 문제의 결과를 저장하고 재사용함으로써 계산의 효율성을 높입니다.

여기서 부분 문제의 결과값을 저장하는 것을 메모이제이션(Memoization)이라고 합니다.

• 결과 재사용: 한 번 계산한 문제의 결과를 저장하고 재사용하여, 중복 계산을 방지합니다.

• 부분 문제 최적화: 큰 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법들로 구성됩니다.

분할 정복은 문제를 더 작은 부분으로 나누어 각각 독립적으로 해결하고, 이를 결합하여 전체 문제를 해결하는 전략입니다.

• 분할: 큰 문제를 작은 문제로 분할합니다.

• 정복: 각 작은 문제를 독립적으로 해결합니다.

• 결합: 해결된 작은 문제들을 결합해 전체 문제의 해답을 찾습니다.

• 문제의 중복성: 동적 계획법은 중복되는 부분 문제를 해결하는 데 효율적입니다. 반면, 분할 정복은 하위 문제가 서로 중복되지 않을 때 더 효과적입니다.

• 메모리 사용: 동적 계획법은 계산된 결과를 저장하기 위해 추가 메모리를 사용합니다. 하지만 분할 정복은 일반적으로 이러한 저장 공간을 필요로 하지 않습니다.