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

동적계획법과 분할정복은 서로 비슷한 듯 다릅니다. 이번 시간에 동적계획법과 분할정복에 대해서 자세히 알아봅시다

 

동적계획법은 Dynamic Programming으로 흔히 DP라고 부릅니다. 

동적계획법은 큰 문제를 해결하기 전, 작은 문제부터 해결해서 해당 해를 이용해 큰 문제를 풀어나가는 상향식 접근 방법입니다. 

작은 문제의 결과값으로 큰 문제를 해결해나가는 것입니다. 

동적계획법은 Memozation 기법을 활용합니다. 

Memozation 기법이란 컴퓨터가 이전에 계산한 값을 저장해 두어 다시 계산할 필오 없게 해서 전체의 실행 속도를 높이는 것을 말합니다. 

이처럼 작은 문제의 결과값을 저장해서 큰 문제를 해결할 때 재활용해서 사용합니다. 

이런 특성을 가지고 있기 때문에 피보나치 수열 등에 활용할 수 있습니다. 

 

분할정복은 큰 문제를 나눌수 없는 작은 부분까지 나뉘어 그 작은 부분을 해결해 나간 후, 그것들을 합쳐서 큰 문제를 해결합니다. 

동적계획법과 비슷하지만 다른 부분은 작은 문제의 결과값을 재활용하지는 않는 것입니다. 

큰문제의 해답을 구하기 위해 아래로 내려가면서 작은 문제를 구하고, 최종적으로 합쳐서 사용합니다. 

분할정복은 구현을 위해 재귀함수를 사용합니다. 

분할정복은 퀵정렬, 병합정렬에 사용됩니다. 

 

듣고도 동적계획법이랑 분할정복이 서로 어떻게 다른지,, 또 재귀용법이랑 차이가 있는지 잘 모르겠죠?(저도 그랬답니다 하하)

동적계획법은 아주 작은 문제부터 풀어서 위로 올라갑니다 그래서 0, 1,-> 1 -> 2 -> 3 -> 5-> ... 이런 피보나치 처럼요

분할정복은 크게 시작해서 작게 쪼개는 과정을 반복합니다. 100 -> 50, 50 -> 25, 25, 25, 25 -> ... 이렇게요, 

위의 예시를 봤을 때 동적계획법은 작은 문제의 해결 결과들이 재사용됨을 볼 수 있고, 분할정복은 결과들이 재사용되지 않음을 확인할 수 있어요

그래서 동적계획법은 작은 문제의 해결 결과들을 다시 계산할 필요 없이 memozation 하는 과정이 필요합니다. 

분할정복은 계속 1/2씩 나누는 과정이 반복되어야 하니, 1/2를 나누는 함수를 재귀적으로 호출한다면 문제가 해결되겠죠?

 

저의 글이 동적계획법과 분할정복이 아리까리한 사람들에게 도움이 되었으면 좋겠습니다~