[알고리즘] 동적계획법(DP)과 분할정복(DC)

동적계획법 (Dynamic Programming)과 분할정복 (Divide and Conquer)

 

1. 정의

동적계획법 (DP)

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결하고 최종적으로 전체 문제를 해결하는 알고리즘입니다.
• 상향식 접근법으로 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식입니다.
• Memoization 기법을 사용합니다.
• Memoization 이란, 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행속도를 빠르게 하는 기술입니다.
• 문제를 쪼갤 때 부분 문제는 중복되어 재활용됩니다.
• ex. 피보나치 수열 f(n) = f(n-1) + f(n-2)

분할 정복 (DC)

• 문제를 나눌 수 없을때까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘입니다.
• 하향식 접근법으로 상위의 답을 구하기 위해 아래로 내려가면서 하위의 답을 구하는 방식입니다.
• 일반적으로 재귀함수로 구현합니다.
• 문제를 쪼갤 때, 부분문제는 서로 중복되지 않습니다.
• ex. 병합정렬, 퀵정렬

2. 공통점과 차이점

 

공통점

• 문제를 잘게 쪼개서 가장 작은 단위로 분할합니다.

차이점

• 동적계획법(DP)
• 부분 문제는 중복되어 상위 문제 해결 시 재활용됩니다.
• 메모리제이션 기법을 사용합니다. (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)

• 분할정복(DC)
• 부분 문제는 서로 중복되지 않습니다.
• 메모리제이션 기법을 사용하지않습니다. 

3. 동적계획법 코드

DP는 메모리제이션 기법을 사용하기때문에 작은 부분 문제의 해답을 메모해두어야합니다.