참고
분할정복
NOTE
•
알고리즘 디자인 패러다임 중 하나
•
문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제(Sub-problem)들로
나누고(Divide), 문제를 해결(Conquer)한 다음 그 결과를 이용해 다시 전체 문제를 해결
•
예시
◦
정렬문제 ( 퀵 정렬 , 병합 정렬
◦
큰 숫자 곱하기(Karatsuba 알고리즘) : n자리 수 2개를 곱하여 결과를 나타내는 알고리즘
◦
이진 탐색 (Binary-search)
◦
Closet Pair of Points 문제 : 모든 Point의 쌍의 거리 중 최소거리 찾기
◦
Strassens’s 알고리즘 : 두 행렬을 곱하는 효과적인 알고리즘
◦
Colley-Turkey Fast Fouier Tansform(FFT) 알고리즘 : 가장 일반적인 FFT 알고리즘
•
핵심
◦
분할 : 동일한 타입의 하위 문제로 큰 문제를 분할
◦
정복 : 재귀적으로 하위문제들을 해결
◦
병합 : 적절히 해결된 결과를 사용해 큰 문제를 해결
병합정렬
NOTE
•
분할 : 전체 데이터를 반으로 지속적으로 분할한다 (직접 문제가 해결되는 수준까지)
•
정복 : 데이터가 1개가 남으면 그 자체로 이미 정렬된 상태임.
분할된 2개의 데이터 정렬 (하위문제 해결)
•
병합 : 정렬된 하위 문제를 병합하여 전체 내역을 정렬
이진탐색
NOTE
•
정리된 배열 또는 정리된 리스트에 적합한 고속 탐색방법
◦
시작과 끝의 중앙의 값을 통해서 계속 비교해나감
▪
값이 중앙값보다 크다면 시작값을 중앙 idx + 1로 변경
▪
값이 중앙값보다 작다면 끝의 값을 중앙 idx - 1로 변경
•
성능
◦
시간 복잡도 O(log n)
•
구현
int binarySearch1(int key, int low, int high) {
int mid;
if(low <= high) {
mid = (low + high) / 2;
if(key == arr[mid]) { // 탐색 성공
return mid;
} else if(key < arr[mid]) {
// 왼쪽 부분 arr[0]부터 arr[mid-1]에서의 탐색
return binarySearch1(key ,low, mid-1);
} else {
// 오른쪽 부분 - arr[mid+1]부터 arr[high]에서의 탐색
return binarySearch1(key, mid+1, high);
}
}
return -1; // 탐색 실패
}
Java
복사
분할정복과 동적 프로그래밍의 차이
NOTE
•
공통점
◦
주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결함
•
차이점
◦
분할정복 : 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰임
◦
동적 프로그래밍 : 동일한 중복이 발생할 경우
•
EX)
◦
병합정렬 수행 시에 작은 하위 문제로 쪼개지지만 중복하여 하위문제가 발생하지는 않는다. (분할된 부분은 모두 독립적이고 동일한 부분 중복 X)
◦
중복된다는건 피보나치 수열과 같은 것을 말함
n = 5일때, n-1, n-2를 구하기 위해 n이 1인 경우까지 내려가야함