분할 정복 알고리즘(Divde and Conquer), 이진검색과 피보나치 수열

분할 정복 알고리즘은 문제를 작은 문제로 분할해서 해결(정복) 하는 방법을 만한다. 나폴레옹이 전쟁에서 사용한 전략에서 유래되었다고 한다. 보통 재귀 함수를 통해 많이 구현이 된다. 많은 예시가 있지만 이진검색을 예로 보겠다. 아래는 이진검색을 재귀적으로 즉, 분할 정복으로 구현한 것이다. public static int recursiveBinarySearch(int low, int high) { // 재귀적 이진검색 if(low > high) // 최솟값이 최댓값보다 커지면 return -1; // 위치를 못 찾은 것이므로-1 반환 int mid = (low + high) / 2; // 이진검색을 위해 중간값을 선언 if(key == s[mid]) // 값을 찾을 경우 return mid; // 위치를 반환 else if (key < s[mid]) // 값을 못 찾았는데 찾는 값이 현재의 값보다 작으면 return recursiveBinarySearch(low, mid - 1); ...

원문링크 : 분할 정복 알고리즘(Divde and Conquer), 이진검색과 피보나치 수열