알고리즘 - 합병정렬 1개가 남을 때까지 나눈다.(DIVIDE), 합친다. mergesort 와 merge는 2:1의 관계에 있다. 재귀이기 때문에 -> 스택을 이용한다. mergesort함수의 소스코드 void mergesort(int n, keytype S[]){ if(n>1){ const int h = n/2, m = n-1; keytype U[h], V[m]; for(int I = 0; i

알고리즘 - 분할정복 1) 분할 : 해결하기 쉽도록 문제를 작은 부분으로 나눈다. 2) 정복 : 나눈 작은 문제를 “각각” 해결한다. 3) 통합 : (필요하다면) 해결된 해답을 모은다. 이러한 문제 해결 방법을(top-down)하향식 접근방법 이라고 한다. 이는 이분검색(Binary Search) 재귀 알고리즘을 이용한다. 이분검색은 O(logn)의 복잡도를 가진다. 순차검색이 O(n)이 걸리는 것을 보면 더욱 효율적인 알고리즘인 것을 알 수 있다. 이분검색의 설계전략: 1) x가 배열의 중간에 항목과 같으면 빙고 그렇지 않으면: 분할 : 배열을 나누어서 x가 중앙보다 작으면 왼쪽에 위치한 반쪽을 선택하고 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택한다. 2) 정복 : 선택된 반쪽 배열에서 x를 찾는..