분할정복 알고리즘

분할정복 알고리즘 (Divide - and - Conquer)

정의

- 문제의 입력을 분할하여 subproblem을 만든 후 해를 구하는 알고리즘을 subproblem에 적용하여 계산, 해 취합하여 본 문제의 해를 구하는 알고리즘

- 분할은 더이상 할 수 없을때까지 진행 한다.

- 분할 횟수 구하기 (k):  n(입력)은 계속 2등분되며 1개가 될때까지 분할을 진행 한다. 따라서, n/2^k = 1 이고 k = log2n이다. 

종류 (문제가 a개로 분할, 크기가 1/b로 감소) 

• a=b=2 : 합병정렬, 최근접 점의 쌍 찾기, 공제선 문제 
• a=3, b=2: 큰 정수의 곱셈
• a=4, b=2: 큰 정수의 곱셈
• a=7, b=2: 스트라센의 행렬 곱셉 알고리즘
• a=2, b=일정하지 않음: 퀵 정렬
• a=2, b=2, 하나의 subproblem은 고려되지 않음: 이진탐색
• a=2, b=일정하지 않음, 하나의 subproblem은 고려되지 않음: 선택 문제 알고리즘
• 부분문제의 크기가 1,2개씩 감소: 삽입 정렬, 피보나치 수 계산