동적 계획법, 분할 정복

동적 계획법 (Dynamic Programming)

• 입력 크기가 작은 부분의 문제를 해결한 후, 해당 부분 문제의 해를 활용하여 보다 큰 크기의 부분 문제를 해결하여 전체 문제를 해결하는 알고리즘

• 상향식 접근법으로 최하위 해답을 구하여 저장하고 결과를 이용해서 상위 문제를 풀어가는 방식이다.

• Memoization 기법을 사용

프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 해 실행속도를 빠르게 해준다.

• 문제를 쪼개서 풀거나 중복되거나 재활용될때 사용

분할 정복

• 문제를 나눌 수 없을 때 까지 나누어서 문제를 풀고 다시 병합하여 답을 얻는 알고리즘

• 하향식 접근법으로 상위 해답을 구하기 위해 아래로 내려가면서 하위 해답을 구하는 방식

• 문제를 쪼갤 때 부분 문제는 중복되지 않는다.

공통점

1. 문제를 쪼개서 작은 단위로 분할한다.

차이점

1. 동적 계획법은 부분 문제가 중복되어 상위 문제 해결시 재활용된다.

2. 동적 계획법은 Memoization 기법을 사용한다.

3. 분할 정복은 문제 중복이 안된다.

4. 분할 정복은 Memoization 기법을 사용하지 않는다.