분할정복 알고리즘 vs 다이나믹 알고리즘

-같은 점-

 

작은 부분으로 문제를 나눈다.

 

-다른 점-

 

다이나믹 알고리즘 : 각각의 작은 문제가 겹친다. memoization을 통해 이를 해결한다.

분할정복 알고리즘 : 문제가 겹치지 않는다. 

 

따라서 다이나믹 알고리즘 문제의 경우 재귀함수를 쓰면 시간초과가 많이 나오지만,

분할정복 알고리즘은 재귀함수 사용에 비교적 자유롭다.

 

-대표 문제 -

 

분할 정복 알고리즘 

 

1780번 종이의 갯수

11729번 하노이탑