동적 계획법(Dynamic Programming)이란?
동적 계획법은 복잡한 문제를 작은 부분 문제로 나누고, 각 부분 문제의 결과를 저장하고 재사용함으로써 계산의 효율성을 높입니다.
여기서 부분 문제의 결과값을 저장하는 것을 메모이제이션(Memoization)이라고 합니다.
특징
-
결과 재사용: 한 번 계산한 문제의 결과를 저장하고 재사용하여, 중복 계산을 방지합니다. -
부분 문제 최적화: 큰 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법들로 구성됩니다.
분할 정복(Divide and Conquer)이란?
분할 정복은 문제를 더 작은 부분으로 나누어 각각 독립적으로 해결하고, 이를 결합하여 전체 문제를 해결하는 전략입니다.
특징
-
분할: 큰 문제를 작은 문제로 분할합니다. -
정복: 각 작은 문제를 독립적으로 해결합니다. -
결합: 해결된 작은 문제들을 결합해 전체 문제의 해답을 찾습니다.
차이점
-
문제의 중복성: 동적 계획법은 중복되는 부분 문제를 해결하는 데 효율적입니다. 반면, 분할 정복은 하위 문제가 서로 중복되지 않을 때 더 효과적입니다. -
메모리 사용: 동적 계획법은 계산된 결과를 저장하기 위해 추가 메모리를 사용합니다. 하지만 분할 정복은 일반적으로 이러한 저장 공간을 필요로 하지 않습니다.
다음 내용이 궁금하다면?
코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!