[Algorithm] 분할 정복 (Divide and Conquer)
Divide and Conquer (DAC : 분할 정복)
- 문제를 더이상 나눌 수 없을 때까지 나누고, 나누어진 문제를 각각 개별적으로 풀어 전체 문제에 대한 답을 얻는 알고리즘
- 장점 : 문제를 나누어 풀기 때문에 성능 우수
- 단점 : 재귀 함수를 사용하기 때문에 비용 문제 발생
연산
- Divide 분할 : 원래 문제를 하위 문제로 나눔 (하위 문제의 집합 = 원래의 문제)
- Conquer 정복 : 모든 하위 문제를 개별적으로, 재귀 적으로 해결
- Combine 결합 : 하위 문제의 솔루션을 모아 전체 문제에 대한 솔루션을 얻음
종류
- Merge Sort (병합 정렬)
- Quick Sort (퀵 정렬)
- Binary Search (이진 검색)
- Tower of Hanoi (하노이의 탑)
- Strassen’s Matrix Multiplication (슈트라센 알고리즘)
- Strassen의 알고리즘 은 두 행렬을 곱하는 효율적인 알고리즘
- 두 행렬을 곱하는 간단한 방법은 3 개의 중첩 루프가 필요하며 O (n3)
- Strassen의 알고리즘은 O (n2.8974) 시간에 두 개의 행렬을 곱함
- Closest pair (points) (최근접 점쌍 문제)
- 가장 가까운 점 쌍 문제는 xy 평면의 점 집합에서 가장 가까운 점 쌍을 찾는 문제
- 이 문제는 모든 점 쌍의 거리를 계산하고 거리를 비교하여 최소값을 구함으로써 O (n2) 시간 내에 해결할 수 있음
complexity
- 시간복잡도 : O(nLogn)
자바를 이용하여 divide and conquer - fibonacci 수열 구현 (재귀함수 사용)
public static int fibonacciRecusrion(int n) {
if(n < 2) {
return n;
}else{
return fibonacciRecusrion(n-1) + fibonacciRecusrion(n-2);
}
}
references
https://www.javatpoint.com/divide-and-conquer-introduction
https://www.geeksforgeeks.org/divide-and-conquer-algorithm-introduction/
https://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm