[자료구조 및 알고리즘] CH10. Divide and Conquer

 

Divide and conquer(분할정복)이란?

• 다음의 세 단계를 거치는 알고리즘이다.
  • Divide : large problem을 small subproblem으로 분할
  • Conquer : recursive하게 각 subproblem을 푼다
  • Combine : subproblem의 답을 조합해 large problem의 답을 구한다.

D&C 사용 예시

• [8,2,6,3,9,1,7,5,4,2,8] 리스트 내에서 최솟값, 최댓값을 찾는 문제는 다음과 같이 풀 수 있다.
  
  • 먼저 large set을 두 그룹으로 나누고, 나누어진 그룹에서 다시 두 그룹으로 나누고....이러한 과정을 풀기에 아주 단순한 small set이 될 때까지 반복한다. 즉, set의 원소 갯수 n이 2개 이하가 될 때까지 하는 것이다.(분할)
  • 분할 과정이 다 끝났으면 small set 안에서 min,max를 찾는다
  • 거꾸로 올라가며 subproblem들의 결과를 조합해 large problem의 결과를 얻어낸다.

D&C를 이용하는 예시

• Merge sort, Quick sort
• Binary search
• 최대, 최솟값 찾기

Merge sort 도식화(출처 : https://www.techiedelight.com/merge-sort/)

Quick sort 도식화(출처 : https://www.techiedelight.com/quicksort/)

D&C의 장단점

• 장점
  • 스케일이 크고 복잡한 문제를 좀 더 단순한 문제로 풀어낼 수 있다
  • 대체적으로 단순한 문제를 recursive하게 풀기 때문에 빠르다(ex. mergesort, quicksort)->효율적
• 단점
  • 함수의 재귀적 호출(recursive)로 인한 메모리 차지 오버헤드
  • 중간 데이터를 저장할 별도의 메모리 공간 필요(mergesort와 quicksort의 중간결과를 저장하는 것을 생각해보라!) - 대체적으로 메모리와 스피드는 trade-off 관계에 있다!!