분할 정복(Divide and Conquer)
문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제(Sub-problem)들로 나누고(Divide) 문제를 해결한 다음(Conquer) 그 결과를 이용해 부분 문제를 병합(Combine)하며 문제를 해결하는 방식이다.
분할 정복의 핵심 진행방식은 다음과 같다.
① 분할(Divide): 주어진 문제를 동일한 타입의 하위 문제로 분할한다.
② 정복(Conquer): 재귀적으로 부분 문제들을 해결한다.
③ 병합(Combine): 각 부분 문제의 해결을 결합하여 전체 문제를 해결한다.
분할을 제대로 수행하면 정복이 쉬워지므로 분할의 설계가 중요하다.
분할 정복은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 떨어뜨릴 수 있다.
분할 정복의 특징
- Top-down 재귀방식으로 구현하기 때문에 코드가 직관적이고 간결하다.
- 대규모 문제를 작은 문제들로 나누어 해결하기 때문에 병렬로 문제를 해결하여 효율적이다.
- 재귀 함수 호출로 오버헤드가 발생할 수 있다.
- 스택에 다량의 데이터를 보관할 경우 오버플로우가 발생할 수 있다.
- 분할된 작은 문제는 원래 문제와 성격이 동일하다 -> 입력 크기만 작아짐
- 분할된 문제는 서로 독립적이다(중복 제거 X) -> 순환적 분할 및 결과 결합 가능
분할 정복과 동적 프로그래밍의 차이
- 분할 정복과 동적 프로그래밍은 주어진 문제를 작게 나눠 하위 문제를 해결하고 연계적으로 큰 문제를 해결한다는 점은 공통적이다.
- 동적 계획법은 중복되는 하위 문제들의 해결책을 저장하고 재사용함으로써 효율성을 극대화한다. 반면에 분할 정복은 하위 문제들이 서로 독립적으로 중복이 일어나지 않는다는 가정 하에 작동한다.
- 동적 계획법은 하위 문제의 해결책을 저장하기 위해 추가적인 메모리(일반적으로 배열이나 테이블)를 사용한다. 하지만 분할 정복은 일반적으로 하위 문제들의 해결책을 저장하기 위한 추가적인 메모리를 요구하지 않는다.
- 동적 계획법은 최적화 문제와 카운팅 문제에 자주 사용되며, 분할 정복은 정렬, 탐색, 멀티포인트 계산 등의 문제에 주로 사용된다.
- 분할 정복은 Top-Down 방식만 가능하지만 동적 프로그래밍은 Bottom-up 방식도 가능하다.
1. 퀵 정렬(Quick Sort)
- 배열을 분할하여 정렬하는 방법이다.
- '피벗'이라고 하는 기준 값을 선택한 후 피벗보다 작은 요소들은 왼쪽에, 큰 요소들은 오른쪽에 위치시킨다.
- 이후 왼쪽과 오른쪽 배열에 대해 같은 방식으로 정렬을 반복한다.
- 평균 시간 복잡도는 O(nlogn)이지만, 최악의 경우는 O(n^2)이다.
2. 병합 정렬(Merge Sort)
- 배열을 절반으로 계속 쪼개며 분할한 후, 분할된 배열을 다시 병합하면서 정렬하는 방법이다.
- 병합 과정에서 두 부분 배열의 요소들을 순서대로 비교하고 정렬한다.
- 시간 복잡도는 모든 경우에 O(nlogn)이다.
3. 이진 탐색(Binary Search)
- 정렬된 배열에서 특정 값을 효율적으로 찾는 방법이다.
- 배열의 중간 요소를 선택하고 찾고자 하는 값과 비교한 후, 값이 중간 요소보다 작으면 왼쪽 부분에 대해, 크면 오른쪽 부분에 대해 검색을 계속한다.
- 시간 복잡도는 O(logn)이다.
4. 카라츠바 곱셈(Karatsuba Multiplication)
- 두 큰 숫자를 곱하는 빠른 방법이다.
- 숫자를 분할하여 부분적인 곱셈 문제로 간소화한 후 이 결과를 합쳐 최종 결과를 도출한다.
- 전통적인 곱셈 방법보다 더 적은 수의 곱셈을 필요로 하며, 이로 인해 성능이 향상된다.
- 일반적인 곱셈의 시간 복잡도는 O(n^2)인 반면, 카라츠바 방법은 O(n^1.585)이다.
참고
[알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java)
알고리즘 - 분할정복(Divide & Conquer)
안녕하세요