분할 정복

분할정복 알고리즘

‘큰 문제를 작은 문제로 분할하여 문제를 해결하는 방식’

전반적으로 ‘재귀’와 유사한 점이 많은 방식이다.

• 구체적인 알고리즘??

  ‘분할정복’, ‘그리디’와 같은 경우, 구체적인 구현의 방식을
  표현하지는 않으나, ‘공통된 해결방식’이라는 점을
  공유하는 면에서 ‘알고리즘’ 보다
  ‘기법’ 혹은 ‘패러다임’ 이라고 기술되는 경우도 있으니 참고
  

분할정복의 설계

1. Divide

   문제를 더 작은 문제로 분할

2. Conquer

   더 이상 분할할 수 없는 경우, 주어진 문제를 해결

3. Combine

   해결된 문제들을 통합하여 원래 문제의 답을 얻는다

분할 정복으로 분류되는 알고리즘

1. 퀵, 병합 정렬
2. Karatsuba 알고리즘(큰 수의 곱셈)
3. 이진 탐색 …

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

두 알고리즘 모두 ‘주어진 문제를 작게 쪼개서 하위문제를 해결하고
연계적으로 큰 문제를 해결한다’는 공통점이 존재한다

분할된 하위 문제에서 ‘동일한’ 중복이 일어나는 경우,
분할정복이 아닌 동적 프로그래밍을 사용한다

각각의 예시로 ‘병합정렬’은 ‘분할정복’ 으로,
‘피보나치 수열’은 ‘동적 프로그래밍’으로 들 수 있다