[알고리즘] 분할정복 v.s. DP(Dynamic Programming)

오늘은 DP와 분할정복에 대해서 알아보겠습니다. 또한 DP와 분할정복이 언뜻 보면 비슷한 것으로 생각할 수도 있는데, 이의 차이점을 조금 명확하게 확인해봅시다.

 

 

   분할정복

분할정복이란 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘입니다.

 

분할정복은 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하고 이들의 해를 취합하여 원래 문제의 해를 얻습니다.

 

 

즉, 하나의 문제를 더 이상 분할할 수 없는 부분 문제로 쪼개고, 해당 부분 문제에 대한 부분 해를 구하여 최종 문제에 대한 해를 구하는 방식이죠.

 

아래의 그림이 분할 정복을 잘 설명해주고 있습니다.

하나의 문제가 부분 문제로 쪼개져서 최종 해를 구합니다.

 

 

   DP(Dynamic Programming)

동적계획 알고리즘 즉, DP는 입력 크기가 작은 부분 문제들을 해결한 후에, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 문제해결 방식을 의미합니다.

 

 

DP는 큰 부분 문제를 해결하기 위해 작은 부분 문제의 해를 여러 번 사용하기도 합니다. 하지만 이러한 관계는 문제나 입력에 따라 다르고, 대부분의 경우 뚜렷하게 확인하기가 힘듭니다. 따라서 이러한 관계를 함축적 순서라고 합니다.

 

 

   분할정복 v.s DP

그렇다면 이 둘은 상당히 비슷해보입니다. 두 알고리즘 다 어떤 문제 해결을 위해 작은 문제로 쪼개고 해당 결과를 이용하는 것 같으니까 말이죠.

 

 

하지만 명확한 차이가 있습니다.

바로, 부분 문제에 대한 재사용 여부 입니다.

 

앞서 말했듯이 분할 정복은 부분 문제를 재사용하지 않습니다. 하지만 DP는 부분문제를 여러번 사용할 수도 있는 관계가 존재하므로 명확한 차이점이 존재함을 알 수 있습니다.

 

분할 정복 알고리즘과 동적 계획 알고리즘

 

 

 

 

 

오늘은 분할 정복과 DP에 대해 알아봤고, 그 차이점에 대해 명확하게 알아봤습니다. 감사합니다.