분할 정복 알고리즘 복잡한 문제를 더 작고 관리하기 쉬운 부분으로 나누고 각 부분을 개별적으로 해결한 다음 솔루션을 결합하여 원래 문제를 해결하는 문제 해결 전략입니다. 컴퓨터 과학 및 수학 분야에서 널리 사용되는 알고리즘 기술입니다.

예: 에서 병합 정렬 알고리즘, 분열과 정복 strategy는 요소 목록을 정렬하는 데 사용됩니다. 아래 이미지는 다음을 사용하여 배열을 정렬하기 위한 분할 및 병합 상태를 보여줍니다. 병합 정렬 .

내용의 테이블

• 분할 정복이란 무엇인가?
• 분열과 정복의 단계
• 분할 정복의 응용
• 분할 정복의 기본
• 분할 정복에 관한 표준 알고리즘
• 이진 검색 기반 문제
• 분할 정복 연습 문제

분할 정복 알고리즘이란 무엇입니까?

분할 정복은 더 큰 문제를 하위 문제로 나누고, 하위 문제를 독립적으로 해결하고, 이러한 하위 문제의 솔루션을 결합하여 더 큰 문제의 솔루션을 얻는 문제 해결 기술입니다.

분할 정복 알고리즘의 단계:

분할 정복 알고리즘은 세 단계로 나눌 수 있습니다. 나누다 , 정복하다 그리고 병합 .

1. 나누기:

• 원래 문제를 더 작은 하위 문제로 분해합니다.
• 각 하위 문제는 전체 문제의 일부를 나타내야 합니다.
• 목표는 더 이상의 분할이 불가능할 때까지 문제를 분할하는 것입니다.

2. 정복:

• 각각의 작은 하위 문제를 개별적으로 해결하세요.
• 하위 문제가 충분히 작은 경우(종종 기본 사례라고 함) 추가 재귀 없이 직접 해결합니다.
• 목표는 이러한 하위 문제에 대한 솔루션을 독립적으로 찾는 것입니다.

3. 병합:

• 하위 문제를 결합하여 전체 문제의 최종 솔루션을 얻습니다.
• 작은 하위 문제가 해결되면 해당 솔루션을 재귀적으로 결합하여 더 큰 문제의 솔루션을 얻습니다.
• 목표는 하위 문제의 결과를 병합하여 원래 문제에 대한 솔루션을 공식화하는 것입니다.

분할 정복 알고리즘의 응용:

• 병합 정렬: 병합 정렬은 분할 정복 정렬 알고리즘의 전형적인 예입니다. 배열을 더 작은 하위 배열로 나누고 개별적으로 정렬한 다음 병합하여 정렬된 배열을 얻습니다.
• 중앙값 결과: 숫자 집합의 중앙값은 분할 정복 접근법을 사용하여 찾을 수 있습니다. 집합을 더 작은 하위 집합으로 재귀적으로 나누면 중앙값을 효율적으로 결정할 수 있습니다.
• 최소 및 최대 결과: Divide and Conquer 알고리즘을 사용하면 배열의 최소 요소와 최대 요소를 동시에 찾을 수 있습니다. 배열을 절반으로 나누고 각 절반의 최소-최대 쌍을 비교함으로써 전체 최소값과 최대값을 로그 시간 복잡도로 식별할 수 있습니다.
• 행렬 곱셈: Strassen의 행렬 곱셈 알고리즘은 행렬을 더 작은 부분행렬로 나누고 그 곱을 결합하여 큰 행렬에 필요한 곱셈 횟수를 줄이는 분할 정복 기술입니다.
• 가장 가까운 쌍 문제: 가장 가까운 쌍 문제는 다차원 공간의 점 집합에서 가장 가까운 두 점을 찾는 것입니다. 가장 가까운 쌍 분할 및 정복 알고리즘과 같은 분할 및 정복 알고리즘은 점을 재귀적으로 분할하고 하위 문제의 솔루션을 병합하여 이 문제를 효율적으로 해결할 수 있습니다.

분할 정복 알고리즘의 기본:

• 분열과 정복 소개
• 동적 프로그래밍과 분할 정복
• 감소와 정복
• 분할 정복 반복에 대한 고급 마스터 정리

표준 알고리즘 분할 정복 알고리즘 :

• 이진 검색
• 병합 정렬
• 빠른 정렬
• pow(x, n) 계산
• 빠른 곱셈을 위한 Karatsuba 알고리즘
• Strassen의 행렬 곱셈
• 볼록 껍질(간단한 분할 정복 알고리즘)
• Convex Hull을 위한 Quickhull 알고리즘

이진 검색 기반 문제:

• 주어진 배열에서 피크 요소 찾기
• 정렬된 배열에서 다수의 요소를 확인하세요.
• 두 개의 정렬된 배열의 K번째 요소
• 0의 개수 찾기
• Rotated Sorted 배열에서 회전 수 찾기
• 단조 증가하는 함수가 처음으로 양수가 되는 지점을 찾습니다.
• 두 개의 정렬된 배열의 중앙값
• 서로 다른 크기로 정렬된 두 배열의 중앙값
• 이진 검색을 이용한 화가의 파티션 문제

연습문제 분할 정복 알고리즘 :

• 정수의 제곱근
• 최소 비교 횟수를 사용하는 배열의 최대 및 최소
• O(n) 시간 이내에 제한된 범위 배열에서 각 요소의 빈도를 찾습니다.
• 타일링 문제
• 카운트 반전
• 스카이라인 문제
• 행별 및 열별로 정렬된 2D 배열에서 검색
• 최소 페이지 수 할당
• 모듈러 지수화(모듈러 산술의 거듭제곱)

빠른 링크 :

• 데이터 구조와 알고리즘 배우기 | DSA 튜토리얼
• 분할정복에 관한 '연습 문제'
• 분할 정복에 관한 '퀴즈'