분할정복법과 동적프로그래밍

분할 정복법과 동적 프로그래밍의 정의

---

• 분할 정복법(Divide and Conquer)
  • 어떠한 큰 문제를 해결하기 위해 큰 문제를 작은 단위의 문제로 나누어 해결하는 방법 (Top-down)
  • 문제의 크기가 충분히 작아질때까지 반복적으로 분할
  • 해결한 작은 문제를 가지고 바로 윗 단계의 문제를 해결해 나가는 방식
  • 대표적인 예로는 Binary Search와 Merge Sort, Quick Sort 등이 있다.

 

• 동적 프로그래밍(Dynamic Programming)
  • 문제를 작은 인스턴스들로 나누고 Bottom-up 순서로 풀어나가면서 문제의 값을 정해놓고 필요할 때 가져와  문제를 해결하는 방식이다. "기억하며 풀기"라 생각하면 된다.
  • 대표적인 예로는 TSP 문제, 피보나치 수열, 파스칼의 트리 작성 등이 있다.

 

분할정복법과 동적 프로그래밍의 공통점과 차이점

---

• 공통점 : 문제를 작은 단위로 나누어 해결
• 차이점 : 분할정복법은 Top-down 방식이며, 동적 프로그래밍은 Bottom-up 방식이다.

 

분할정복법의 장점, 단점, 특징

---

• 장점 : 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다. 
• 단점 : 함수를 재귀적으로 호출함으로 인해 오버헤드가 발생한다. 또한 스택에 다양한 데이터를 보관하고 있어야 하므로 스택오버플로우가 발생한다.
• 특징 : 분할정복법은 보통 재귀함수를 이용하여 구현하는 것이 일반적이나, 재귀호출을 사용하지 않고 스택, 큐 등의 자료구조를 이용하여 구현하기도 한다.

 

이항 계수

---

이항계수는 분할 정복과 동적 프로그래밍에서 차이점을 서술하기 위해 자주 사용된다.

또한 이항계수란 $n$개의 원소에서 $r$개의 원소를 선택하는 방법의 수를 나타내며 재귀 프로그래밍의 기초가 된다.
이항계수는 수학에서 $_nC_r$로 나타낼 수 있으며, 이항계수 프로그래밍의 해결 방법은 $_nC_r =\ _{n-1}C_{r-1}\ +\ _{n-1}C_r$의 공식으로 이루어진다.

 

위 공식을 재귀적으로 구현할 경우 다음과 같다.

int binomial(int n, int k) {
 if (n == k || k == 0)
     return 1;
 else
     return binomial(n - 1, k) + binomial(n - 1, k - 1);
}

 만약 binomical(5,2)를 계산하면 아래와 같이 동일한 문제들을 중복으로 풀게되어, 부분문제의 중복 문제가 발생한다. 즉, 알고리즘의 효율이 떨어지게 된다.

 

 

위와 같이 중복 계산으로 인해 효율이 떨어지는 것을 보완하기 위해서는, 하위 문제를 이용하여 최종 결과의 해를 도출하는 동적 프로그래밍 방법으로 접근하여 해결할 수 있다. 이전 계산 결과 값을 메모이제이션을 이용하여 풀면 다음과 같이 작성할 수 있다.

int binomial(int n, int k) {
 if (n == k || k == 0)
     return 1;
 else if (arr[n][k] > -1) /* 배열 arr이 -1로 초기화되어 있다고 가정 */
     return arr[n][k];
 else {
     arr[n][k] = binomial(n-1, k) + binomial(n-1, k-1);
     return arr[n][k];
 }
}

* 메모이제이션(Memoization) : 이차원 배열에 인덱스에 해당하는 중복 조합을 저장 후, 만약 해당 인덱스에 값이 존재할경우(캐싱되었을 경우) 앞서 계산했다고 판단하여 해당 값을 반환함으로써 중복 계산을 줄여주는 기술. 즉, 동일 계산의 반복 수행을 제거한다.

 

 

Bottom-up 방식으로 해결할 경우 다음과 같이 작성할 수 있다.

int binomial(int n, int k) {
 for (int i=0; i<=n; i++) {
     for (int j=0; j<=k && j<=i; j++) {
         if (k==0 || n==k)
             arr[i][j] = 1;
         else
             arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
     }
 }
 return arr[n][k];
}

 

Reference

---

[1] https://makefortune2.tistory.com/109

[2] https://kimch3617.tistory.com/entry/알고리즘-분할정복법-Divide-and-Conquer

[3] https://jackpot53.tistory.com/130

[4] https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

[5] https://new93helloworld.tistory.com/91