[학교-알고리즘] 분할 정복(Divide and Conquer) - 이진 검색과 병합 정렬(MergeSort)

분할 정복(Divide and Conquer)

1. step : Divide, 문제를 하나 또는 둘 이상의 인스턴스로 나눈다.
2. step : Conquer, 나눠진 문제가 충분히 작고 해결가능 하다면 해결하고, 그렇지 않으면 다시 나눈다.
3. step : Combine, 필요하다면, 나눠진 문제들을 다시 하나로 합친다.

이진 검색의 분할 정복

• step 0 : If x = S[mid], find x and quit
• step 1  : Divide, 배열을 두개의 하위 배열로 나눈다.
  If x > S[mid], 오른쪽 배열을 선택하고 다시 찾는다.
  If x < S[mid], 왼쪽 배열을 선택하고 다시 찾는다.
• step 2 : Conquer, x가 어느쪽 배열에 있는지 결정한다.

이전에 이진 검색의 슈도코드를 구현했다. 

이번에는 분할 정복 방식의 이진 검색을 해보겠다. 기존의 방법과 다르게 재귀적인 모양이 나타난다.

분할 정복 이진 검색 슈도코드

~~

병합 정렬의 분할 정복

• step 1 : Divide, 배열을 두개의 하위 배열로 나눈다.
• step 2 : Conquer, 각 배열이 충분히 작다면, 정렬한다. 그렇지 않으면 재귀로 다시 나눈다.
  
• step 3 : Combine, 나눠진 단일 배열을 합병하면서 정렬한다.

병합 정렬 슈도코드

~~

Best case time complexity of Merge

• 입력 크기 : h, m, 각 배열의 크기
• 기본 연산 : 서브 배열 U[i] 와 V[j]의 크기 비교

=> Best(h,m) = min(h,m) h 또는 m의 선형 시간, 즉 작은 배열이 기준이 되어서 비교하는 경우 가장 시간 복잡도가 좋다. 하나가 먼저 끝나는 경우

Worst case time complexity of Merge

모든 i, j 마다 비교하는 경우 

ex )  U | 5, 7, ...., 100 |

V | 10, 12, .... 103 |        이런 경우 U의 100 때문에 계속 비교를 하게 된다.

=> Worst(h,m) = h+m-1  // 맨 마지막은 비교하지 않아서 -1

Worst case time complexity of MergeSort

계산해야 함. 복잡함. 

 이렇게 나온다