[알고리즘] 동적 계획법(Dynamic Programming, DP), 분할 정복(Divide and Conquer)

동적 계획법(Dynamic Programming, DP), 분할 정복(Divide and Conquer)의 차이와 정의

1. 정의 및 특징

1) 분할 정복(Divide and Conquer)

정의: 상위 문제를 나눌 수 없을 때까지 분할하여 각 하위 문제를 풀고 다시 합병하여 상위 문제의 답을 얻는 방식의 알고리즘이다.

 

특징

- 하향식 접근법: 상위 문제의 답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식. 즉, 상위 문제의 답을 구하기 위해 이전에 수행해야 하는 절차를 수행하는 방식이다.(재귀함수로 구현)

- 문제를 쪼갤 때, 부분 문제의 중복이 없다.

 

예: 병합 정렬, 퀵 정렬 등

 

 

1) 동적 계획법(Dynamic Programming, DP)

정의: 하나의 큰 문제를 해결하기 위해, 큰 문제를 작은 문제들로 나누어 부분적으로 해결한 후 그로부터 파생된 값인 해를 이용하여 최종적으로 전체 문제를 해결하는 방식의 알고리즘이다.

 

특징

- 가장 최하위 문제의 해답을 구한 후, 이를 이용하여 상위 문제를 풀어나가는 방식인 상향식 접근법이다.

- 큰 문제를 작게 쪼개어 문제를 해결할 때 중복되는 부분이 발생한다면 사용한다.

- 동일한 연산에 대해서는 1번의 연산을 수행하여 저장하여 계산의 중복을 방지한다.

- 중복을 방지하여 전체적인 수행 및 연산시간을 절약하여 실행 속도를 빠르게 한다.

 - 메모이제이션(memoization)을 사용한다.

2023.06.13 - [개발 용어 정리] - [알고리즘] 메모이제이션(memoization)

[알고리즘] 메모이제이션(memoization)

 - 타뷸레이션(Tabulation)을 사용한다.

2023.06.17 - [개발 용어 정리] - [알고리즘] 타뷸레이션(Tabulation)

[알고리즘] 타뷸레이션(Tabulation)

 - 메모이제이션, 타뷸레이션을 사용하지않은 경우의 시간 복잡도: O(n*n)

 - 메모이제이션을 사용할 경우 시간 복잡도: O(n)

 - 타뷸레이션을 사용할 경우 시간 복잡도:  O(1)

 

예: 피보나치 수열, 팩토리얼 등

 

2.  동적 계획법과 분할 정복의 공통점과 차이점

공통점: 큰 문제를 작게 쪼개어 가장 작은 단위로 분할하여 문제를 해결한다.

차이점
 - 동적 계획법: 부분 문제에 중복이 발생할 경우 상위문제 해결 시 재활용하는 memoization을 사용한다.
 - 분할 정복: 부분 문제에 중복이 존재하지 않아 memoization을 사용하지 않는다.

 - 부분 문제에 중복이 발생할 경우 동적 계획법을 사용하고 발생하지 않는 경우 분할 정복을 사용한다.