분할 정복(Divide and Conquer)은 알고리즘 패턴입니다. 알고리즘 방법에서 설계는 대규모 입력에 대해 논쟁을 벌이고 입력을 작은 조각으로 나누고 각 작은 조각에 대한 문제를 결정한 다음 조각별 솔루션을 글로벌 솔루션으로 병합하는 것입니다. 이러한 문제 해결 메커니즘을 분할 정복 전략이라고 합니다.

분할 정복 알고리즘은 다음 세 단계를 사용하는 분쟁으로 구성됩니다.

나누다원래 문제를 일련의 하위 문제로 나눕니다.정복하다:모든 하위 문제를 개별적으로, 재귀적으로 해결하세요.결합하다:전체 문제에 대한 해결책을 얻기 위해 하위 문제의 해결책을 모으십시오.

일반적으로 우리는 다음을 따를 수 있습니다. 분할 정복 3단계 과정으로 접근합니다.

예: 특정 컴퓨터 알고리즘은 Divide & Conquer 접근 방식을 기반으로 합니다.

1. 최대 및 최소 문제
2. 이진 검색
3. 정렬(병합 정렬, 퀵 정렬)
4. 하노이 타워.

분할 정복 전략의 기본:

분할 정복 전략에는 두 가지 기본 원칙이 있습니다.

1. 관계식
2. 정지상태

1. 관계식: 이것은 주어진 기술로부터 우리가 생성한 공식입니다. 공식을 생성한 후 D&C 전략을 적용합니다. 즉, 문제를 재귀적으로 분해하고 깨진 하위 문제를 해결합니다.

2. 정지 조건: Divide & Conquer 전략을 사용하여 문제를 해결할 때, 얼마만큼의 시간 동안 Divide & Conquer를 적용해야 하는지 알아야 합니다. 따라서 D&C의 재귀 단계를 중지해야 하는 조건을 중지 조건이라고 합니다.

분할 정복 접근법의 적용:

다음 알고리즘은 분할 및 정복 기법의 개념을 기반으로 합니다.

이진 검색:이진 탐색 알고리즘은 반구간 탐색(half-interval search) 또는 대수 탐색(logarithmic search)이라고도 불리는 탐색 알고리즘이다. 이는 목표 값을 정렬된 배열에 존재하는 중간 요소와 비교하여 작동합니다. 비교 후 값이 다르면 대상을 포함할 수 없는 절반이 결국 제거되고 나머지 절반에 대한 검색이 계속됩니다. 다시 중간 요소를 고려하여 목표값과 비교해보겠습니다. 목표 값이 충족될 때까지 프로세스가 계속 반복됩니다. 검색을 마친 후 나머지 절반이 비어 있는 것을 발견하면 대상이 배열에 존재하지 않는다고 결론을 내릴 수 있습니다.퀵 정렬:이는 파티션 교환 정렬이라고도 하는 가장 효율적인 정렬 알고리즘입니다. 배열에서 피벗 값을 선택한 다음 나머지 배열 요소를 두 개의 하위 배열로 나누는 것으로 시작됩니다. 파티션은 각 요소를 피벗 값과 비교하여 만들어집니다. 요소가 피벗보다 큰 값인지 작은 값인지 비교한 다음 배열을 재귀적으로 정렬합니다.병합 정렬:비교를 통해 배열을 정렬하는 정렬 알고리즘입니다. 배열을 하위 배열로 나눈 다음 각 배열을 재귀적으로 정렬하는 것부터 시작합니다. 정렬이 완료되면 다시 병합됩니다.가장 가까운 점 쌍:계산 기하학 문제입니다. 이 알고리즘은 n개의 점이 주어지면 미터법 공간에서 가장 가까운 점 쌍을 찾는 것을 강조하므로 점 쌍 사이의 거리가 최소화되어야 합니다.Strassen의 알고리즘:Volker Strassen의 이름을 따서 명명된 행렬 곱셈 알고리즘입니다. 대규모 행렬에서 작업할 때 기존 알고리즘보다 훨씬 빠른 것으로 입증되었습니다.Cooley-Tukey FFT(고속 푸리에 변환) 알고리즘:고속 푸리에 변환 알고리즘은 J. W. Cooley와 John Turkey의 이름을 따서 명명되었습니다. 이는 분할 정복 접근법을 따르며 O(nlogn)의 복잡도를 부과합니다.빠른 곱셈을 위한 Karatsuba 알고리즘:이는 1960년 말 Anatoly Karatsuba가 발명하고 1962년에 출판된 전통 시대의 가장 빠른 곱셈 알고리즘 중 하나입니다. 이러한 방식으로 두 개의 n자리 숫자를 최대 한 자리로 줄여서 곱합니다.

분할 정복의 장점

• Divide and Conquer는 수학 퍼즐인 하노이 탑과 같은 가장 큰 문제 중 하나를 성공적으로 해결하는 경향이 있습니다. 기본적인 아이디어가 없는 복잡한 문제를 해결하는 것은 어려운 일이지만, 분할 정복 접근 방식을 사용하면 주요 문제를 두 부분으로 나눈 다음 재귀적으로 해결하므로 노력이 줄어듭니다. 이 알고리즘은 다른 알고리즘보다 훨씬 빠릅니다.
• 속도가 느린 메인 메모리에 액세스하는 대신 캐시 메모리 내의 간단한 하위 문제를 해결하기 때문에 많은 공간을 차지하지 않고 캐시 메모리를 효율적으로 사용합니다.
• 이는 상대 Brute Force 기술보다 더 능숙합니다.
• 이러한 알고리즘은 병렬성을 금지하므로 수정이 필요하지 않으며 병렬 처리 기능이 통합된 시스템에서 처리됩니다.

분할 정복의 단점

• 대부분의 알고리즘은 재귀를 통합하여 설계되었으므로 높은 메모리 관리가 필요합니다.
• 명시적 스택은 공간을 과도하게 사용할 수 있습니다.
• CPU에 있는 스택보다 엄격하게 재귀가 수행되면 시스템이 충돌할 수도 있습니다.