[SW Expert Academy] Advanced-4 분할정복

분할 정복(Devide and Conquer)은 문제를 여러 개의 작은 부분으로 분할(Device)하고, 각 나눈 문제를 해결한 뒤(Conquer), 해결된 해답을 모우는 과정(Combine)으로 구성된다. 분할 정복 알고리즘의 유래는 다음과 같다. 나폴레옹은 아우스터리치전투에서 연합군 사이를 비집고 들어가 연합군을 둘로 분할시킨 다음, 각각 격파하였다고 한다. 

분할 정복 대표 문제로 merge sort, quick sort가 있다. merge sort는 O(nlogn)을 보장하는 반면, quick sort은 보통 O(nlogn)이지만, pivot 선택에 따라 worst case에서는 O(n^2)이 나올 수 있다. merge sort는 정렬 알고리즘의 병렬화가 가능해서 병렬 프로그래밍에 유리한 반면, quick sort는 매우 큰 입력 데이터에 대해 좋은 성능을 보인다.

 플로우 1.거듭제곱 구하기 2. merge sort 3. quick sort 4. binary search

1. 거듭제곱 구하기
-C^n을 구한다고 하면, 단순하게 C를 n번 곱하여 구할 수 있다. 이 때 시간복잡도는 O(n)이 된다. 
-이 시간 복잡도를 O(log(n))으로 줄일 방법은 없을까?
-분할 정복 기반의 수도 코드

Recursive_Power(x, n):
 if n == 1 : return x
 if n is even:
  y <- Recursive_Power(x, n/2)
  return y*y
 else:
  y <- Recursive_Power(x, (n-1)/2)
  return y*y*x

-분할 정복 문제는 recursive 함수에 대입하여 생각하자.

2. merge sort

1) 전체 자료의 집합을 둘로 분할한다.

2) 분할된 두 집합을 정렬된 집합으로 merge한다.

->전체 자료는 최소 부분집합이 될 때 까지 계속해서 먼저 분할(devide)할 것이며, 분할된 집합끼리 merge가 된다. 분할된 부분집합은 이미 정렬되어 있으며, caller은 이 둘을 정렬하여 병합(merge)시키기만 하면 된다.

->분할되는 부분집합이 자식 노드가 되는 트리로 보면, 트리의 높이는 log(n), 같은 높이에서 노드들을 병합하는 데에는 n만큼 걸린다. 따라서 복잡도는 O(nlogn)이 걸린다.

-수도 코드

merge_sort(LIST m)

 if length(m) == 1: return m

 LIST left, right

 middle <- length(m) / 2

 for x in m before middle:

  add x to left

 for x in m after or equal middle:

  add x to right

 left <- merge_sort(left)

 right <- merge_sort(right)

 return merge(left, right)

merge(LIST left, LIST right):

 LIST result

 while length(left) > 0 or length(right) > 0:

  if length(left) > 0 and length(right) > 0:

   if first(left) <= first(right):

    append popfirst(left) to result

   else:

    append popfirst(rigth) to result

  elif length(left) > 0:

   append popfirst(left) to result

  elif length(right) > 0:

   append popfirst(right) to result

  return result

-merge sort의 수도코드는 확실하게 암기하기. 이를 기반으로 다양한 분할 정복 문제를 풀 수 있다. 

3. quick sort

-pivot을 기준으로 분할 때 어느정도 정렬을 수행함

-병합할때 정렬하는 merge sort와는 달리, 분할할 때 정렬을 한다.

-수도 코드

quickSort(A[], l, r):

 if l < r:

  s <- partition(A, l, r)

  quickSort(A[], l, s-1)

  quickSort(A[], s+1, r)

partition(A[], l, r):

 p <- A[l] //pivot

 i <- l, j <- r

 while i <= j:

  while A[i] <= p : i++

  while A[j] > p : j--

  if i < j : swap (A[i], A[j])

 swap (A[l], A[j])

 return j

partition2(A[], l, r):

 x <- A[r]

 i <- l-1

 for j <- i to r-1:

  if A[j] <= x:

   i++

   swap(A[i], A[j])

 swap(A[i+1], A[r])

 return i+1

-pivot 선택이 최소값이나 최대값이면? 

-> 피봇이 왼쪽끝이나 오른쪽끝에 위치하여 분할되지 않는다. -> O(n^2)

-> pivot은 중간값이 될수록 유리하다.

4. 이진 검색

-정렬된 집합에서 특정 원소를 찾는다.

-특정 원소가 없을수도 있으니 이를 고려해서 코드를 짜야함.

-수도 코드

binary_search(n, S[], key):

 low <- 0 

 high <- n-1

 while low <= high:

 mid <= (low+high)/2

 if S[mid] == key:

  return key

 elif S[mid] > key:

  high <= mid-1

 else 

  low <= mid+1

 return -1

binary_search2(S[], low, high, key):

 if low > high:

  return -1

 else:

  mid = (low+high)/2

  if key == S[mid]:

   return mid

  elif key < S[mid]:

   return binary_search2(S[], low, mid-1, key)

  else:

   return binary_search2(S[], mid+1, high, key)

Reference
https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AV3Fu8sqANIBBAQ3