분할 정복 기법

분할 정복(Divide and Conquer)

• 하나의 문제를 여러 개의 작은 부분 문제로 나누고, 이 부분 문제들을 각각 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략
• 분할 된 부분 문제가 충분히 작지 않으면, 분할 정복을 연속으로 적용하면 되는데 보통 순환 호출을 사용한다
• 축소 정복은 분할 한 후에 부분문제가 하나만 남는 특별한 경우의 분할 정복이다.
  ex) 이진 탐색은 분할된 두 부분에서 한쪽은 필요가 없기 때문에 문제의 크기가 절반으로 축소되는 것
• 분할 정복 기법의 문제 해결 순서
1. 분할(Divide)
• 주어진 문제를 같은 유형의 부분문제들로 분할
2. 정복(Conquer)
• 부분문제들을 해결하여 부분 해를 만듦
3. 병합(Combine)
• 부분적인 결과들을 묶어 최종 해를 만듦

병합 정렬(Merge Sort)

• 하나의 리스트를 같은 크기의 두개의 부분 리스트로 분할 하고 각 부분 리스트를 정렬한 다음, 다시 병합하는 전략
• 병합 정렬의 처리과정
1. 분할(Divide)
• 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할
2. 정복(Conquer)
• 부분 리스트를 정렬한다. 이때, 부분 리스트의 크기가 충분히 작지 않으면 순환 호출하여 다시 분할한다. 리스트의 크기가 1이면 이미 정렬(정복) 된것이다.
3. 병합(Combine, merge)
• 정렬된 부분 리스트들을 하나의 배열에 통합한다.
• Python code

  def merge_sort(A, left, right):
      if left < right:
          mid = (left + right) // 2
          merge_sort(A, left, mid)
          merge_sort(A, mid + 1, right)
          merge(A, left, mid, right)
  
  def merge(A, left, mid, right):
      k = left
      i = left
      j = mid + 1
      while i <= mid and j<= right:
          if A[i] <= A[j]:
              sorted[k] = A[i]
              i, k = i + 1, k + 1
          else:
              sorted[k] = A[j]
              j, k = j + 1, k + 1
  
      if i > mid:
          sorted[k : k + right - j + 1] = A[j : right + 1]
      else:
          sorted[k : k + mid - i + 1] = A[i : mid + 1]
  
      A[left : right + 1] = sorted[left : right + 1]

• 복잡도 분석
• 입력 데이터의 구성에 상관없이 동일한 시간에 정렬 됨.
• 점근적 복잡도는 O(nlog 2 n)로 매우 효율적임
• 입력 리스트의 크기와 같은 임시 리스트를 필요로 함
• 따로 공간이 필요하기 때문에 주 메모리보다 속도가 느린 보조 메모리에 있는 파일을 정렬하는 상황 등에서 유용함

퀵 정렬(Quick Sort)

• 평균적으로 매우 빠른 수행 속도를 자랑하는 알고리즘
• 병합 정렬이 항목의 위치에 따라 분할하는 것과 다르게 항목의 값에 따라 분할함
  따라서 리스트가 균등하게 분할 되지 않음
• 퀵 정렬의 처리과정
• 분할(Divide)
• 먼저 피봇(Pivot)을 선택함. 일반적으로 리스트의 첫 번째 항목을 사용함. 피봇보다 작은 값은 전부 피봇의 왼쪽으로, 큰 값은 오른쪽으로 옮긴다
• 정복(Conquer)
• 분할 된 각각의 리스트에 다시 분할 정복 전략을 사용한다.
• 결합(Combine, merge)
• 분할을 할 때 마다 피벗을 중심으로 값들이 나누어지기 때문에 분할과 정복이 끝나면 그 자체가 정렬이 완료된 상태가 됨
• Python code

  def quick_sort(A, left, right):
      if left < right:
          mid = partition(A, left, right)
          quick_sort(A, left, mid - 1)
          quick_sort(A, mid + 1, right)
  
  def partition(A, left, right): 
      low = left + 1 
      high = right 
      pivot = A[left] 
      while (low <= high): 
          while low <= right and A[low] < pivot : low += 1 
          while high >= left and A[high] > pivot : high -= 1 
          
          if low < high : 
              A[low], A[high] = A[high], A[low] 
      A[left], A[high] = A[high], A[left] 
      return high

• 복잡도 분석
• 최선의 경우
• 정렬이 항상 리스트의 가운데서 이루어지는 상황
\
• O(nlog 2 n)
• 최악의 경우
• 리스트가 계속 불균형하게 나누어지는 상황 또는 이미 정렬된 리스트가 최악
• O(n^2)

이진트리

• 모든 노드가 2개의 서브 트리를 갖는 트리.
  서브트리는 공집합일 수도 있다.
• 이진 트리 정의 자체가 같은 구조의 두 서브 트리로 나누는 방식이므로 분할 정복 전략을 바로 적용 할 수 있음.
• 트리의 높이를 구하는 방법
• 분할(Divide)
• 트리를 루트의 왼쪽 서브트리와 오른쪽 서브트리로 나눈다.
• 정복(Conquer)
• 각 서브트리의 높이를 구한다. 만약 서브 트리가 공백이면 높이가 0이고 단말 노드이면 1이다. 그렇지 않다면 문제의 크기가 충분히 작아지지 않은 것이기 때문에 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.
• 결합(Merge)
• 서브 트리의 높이가 구해지면 전체 트리의 높이는 이들 중 큰 값에 1을 더한 것과 같다
• 복잡도 분석
• 점근적 시간 복잡도는 O(n)
• 이진 트리의 표준 순회 문제
• 순회는 트리의 모든 노드를 한 번씩 방문하는 작업
• 루트를 방문하는 작업을 V, 왼쪽 방문을 L, 오른쪽 방문을 R이라고 할때 순회 방법은 아래와 같다.
• 전위 순회(PreOrder Traversal) : VLR
• 중위 순회(Inroder Traversal) : LVR
• 후위 순회(Postorder Traversal) : LRV
• 이진 트리의 표준 순회 문제

최근접쌍의 거리 문제(심화)

• 억지 기법에서는 평면에서 가장 가까운 두점의 거리를 O(n^2) 시간에 계산함.
• 분할 정복 전략을 사용하려면 모든 점들이 x 좌표를 기준으로 오름차순으로 정렬되어 있어야 함
• 분할 정복 전략
• 분할(Divide)
• 리스트를 두 개의 부분 리스트로 분할 한다.
• 정복(Conquer)
• 분할된 리스트의 크기(점들의 개수)가 3 이하인 경우는 바로 계산(정복)한다. 4개 이상인경우 다시 분할 정복 기법을 사용한다.
• 결합(Combine, merge)
• 최종 결과는 분할된 리스트의 답과 양쪽 리스트에 걸쳐있는 점에 의한 거리 중에 가장 작은 값이 되어야 한다.
• 양쪽 리스트에 걸쳐 있는 점은 분할된 면을 기준으로 분할된 리스트의 답보다 먼 거리에 있는 점들은 고려할 필요가 없다.
• 최근접쌍의 거리 문제
• 복잡도 분석
• 점근접 복잡도는 O(nlog 2 n)
• 최근접 쌍의 거리를 이용하는 분야는 그래픽스나 컴퓨터 비전, 항공 트래픽 제어, 지리정보 시스템 등에서 사용함

분할 정복 기법 적용에 대한 고찰

• 분할 정복 기법은 같은 부분 문제가 여러 번 반복되어 나타나지 않을 때 사용해야 한다.
  같은 부분문제가 여러 번 반복되어 나타난다면 동적 계획법을 사용하는 것이 좋다.