분할정복과 동적 프로그래밍
분할 정복
- 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 업는 알고리즘이다.
- 하향식 접근법으로, 상위의 해답을 구하기 위해서 작은 단위인 아래로 내려가면서 하위의 해답을 먼저 구하는 방식이다.(일단적으로 재귀함수로 구현함)
- 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음(예 : 병합 정렬, 퀵 정렬 등)
동적프로그래밍
- 입력의 크기가 작은 부분 문제들을 '해결'한 후에 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 문제를 해결하여 최종적으로 전체 문제를 해결하는 알고리즘이다.
- 상향식 접근법으로 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식이다.
- 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않으며 전체 실행 속도를 빠르게 만드는 기술인 Memoization 기법을 사용한다.
- 문제를 잘게 쪼갤 때, 부분 문제는 중복 되어 재활용된다. (예 : 피보나치 수열)
이 두 방법은 뭐가 다르지..?
우선 방향성이 조금은 다르다 분할 정복과 동적프로그래밍의 특징을 살펴보면 큰 문제인 것을 작은 문제로 나누어서 생각하는거 까지는 같은 특성이라고 볼 수도 있지만 검색을 해보면 든 생각은 비슷하긴 하지만 확실히 다른 특성이라고 생각이 되었다.
- 먼저 동적 프로그램은 memorization 즉, 작은 단위 문제의 답을 저장 해두었다가 꺼내 쓰는 방식인 것이다. 큰 문제를 작은 문제로 나누어 생각한다기 보다 작은 부분 부터 풀어나가 이것의 값을 이용해서 크고 복잡한 문제의 답을 낼때에 작은 과정들에서 빠르게 답만 가져온다라는 것이다.
- 이러한 특성 때문에 bottom-up 방식이라고 하는 것이다.
- 대표적인 예시로는 피보나치 수열이 있다.
- 다음으로 분할 정복 방식은 동적 프로그래밍과는 달리 시작의 큰 문제 에서 파고 들어 문제를 작게 만든 후에 그 작은 문제부터 연쇄적으로 풀며 답을 도출하는 방식이라고 생각이 들었다.
- 큰 문제를 파고 드는 방식이기 때문에 top-bottom 방식이라 칭하는것 같다.
- 대표적인 예로는 퀵 정렬과 병합 정렬이 있다.
두 방법의 예시로 든 퀵 정렬과 병합 정렬은 후에 정렬을 정리할때 천천히 살펴보도록 하겠다. 그때 피보나치 수열 또한 간단하게 보도록 하겠다.
이번 동적 프로그래밍을 공부하며 분할정복에 대해서도 알게되어 이렇게 비교하는 방식으로 정리를 해보았다. 내가 이해한것이 정확한 것인지는 모르겠지만 그래도 동적프로그래밍과 비슷한 분할 정복을 알았다는 것, 이 둘의 차이점을 비교 해볼 수 있었던 것에 만족한다.
