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

Dynamic Programming(동적계획법)과 Divide and Conquer(분할 정복)의 차이를 알아보자.

 

차이를 알아보기에 앞서 동적계획법을 알아보자.

Dynamic Programming(동적 계획법)

Dynamic Programming은 최적화와 연관이 있어, 'Dynamic Optimization'으로 불리기도 한다. 그러면, Dynamic Programming이 도대체 성능과 어떠한 연관이 있는 것일까?

Dynamic Programming 알고리즘은 복잡해 보이는 문제를 하위의 작은 문제들로 쪼개고, 하위 문제들의 결과를 별도의 저장공간에 저장을 한다. 이렇게 함으로써, 동일한 하위 문제가 나왔을 때 중복해서 계산을 할 필요가 없도록 한다.

 

좀 더 나은 이해는 이전 포스팅인 피보나치 문제를 참고하면 될 것 같다.

https://wonillism.tistory.com/20

[Programmers - lv02] 피보나치 수 (cpp / python)

알고리즘 문제를 많이 접하다 보면, 동적계획법과 분할 정복과 차이가 궁금해질 수 있다.

Dynamic Programming VS Divide and Conquer

큰 문제를 작은 단위로 나누어 해결하는 방법은 분할정복 방식(Divide-conquer)과 유사하다. Dynamic Programming의 문제해결 방법이 Divide-conquer 방식과 다른 점은, 하위 문제가 중복해서 발생하게 되면 중복된 문제는 한 번만 연산을 하고 이후 같은 문제를 마주쳤을때 기억하고 있던 결괏값을 가지고 와 처리한다는 것이다.

https://chanwhe-kim.netlify.app/blog/dynamic-programming/

 위 그림을 참고하고, 좀 더 생각해보자.

내 생각에 엄밀히 말하면 Dynamic Programming은 Divide and Conquer 방식의 확장 죽, DP > DC 라고 생각하는게 더 좋을 것 같다.

 

둘 다 문제를 재귀적으로 동일하거나 관련된 유형의 두 개 이상의 하위 문제를 직접 해결할 수 있을 정도로 단순해질 때까지 분해하고, 그런 다음 하위 문제에 대한 솔루션을 결합하여 원래 문제에 대한 솔루션을 제공한다.

그렇다면 왜 여전히 다른 패러다임 이름을 가지고 있고 왜 동적 프로그래밍을 확장이라고 생각할 수 있을까? 동적 프로그래밍 접근 방식은 문제가 특정 제한 사항이나 전제 조건이 있는 경우에만 문제에 적용될 수 있기 때문이다. 그리고 그 후 동적 프로그래밍은 memoization 또는 tabulation을 사용하여 분할 및 정복 접근 방식을 확장한다.

동적 프로그래밍 전제 조건/제한 사항

동적 프로그래밍이 적용되기 위해서는 문제를 분할하고 정복하는 두 가지 핵심 속성이 있어야 한다.

일단 이 두 가지 조건이 충족되면 이 분할 정복 문제는 동적 프로그래밍 접근 방식을 사용하여 해결할 수 있다고 말할 수 있을 것 같다.

 

분할 및 정복을 위한 동적 프로그래밍 확장
동적 프로그래밍 접근은 성능을 크게 향상시킬 수 있는 하위 문제 솔루션을 저장하고 재사용하는 목적을 가진 두 가지 기술(memoization 및 tabulation)을 사용하여 분할 정복 접근을 확장합니다. 예를 들어 피보나치 함수의 순진한 재귀 구현은 O(2^n)의 시간 복잡도를 가지며 여기서 DP 솔루션은 O(n) 시간으로 동일한 작업을 수행한다다.
memoization은 이전에 계산된 결과를 저장하고 재사용하는 기술을 나타낸다.

 

 

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95