축소 정복 기법

축소 정복(Decrease-and-Conquer) 기법

• 주어진 문제를 해결하기 위해 이 문제와 좀 더 작은 문제간의 관계를 이용하는 전략
• 문제 사이의 관계가 구해지면 하향식(Top-Down)이나 상향식(Bottom-Up)으로 적용할 수 있다.
  하향식은 보통 순환구조를 이용하고 상향식은 반복구조로 표현하며 점증적(Incremental) 기법이라고도 한다.
• 축소 정복 기법은 분할 정복 기법의 한가지 유형으로도 볼 수 있음
• 문제의 크기가 줄어드는 방식에 따른 3가지 유형
• 고정 크기 축소(Decrease by a constant)
• 순환이나 반복에 따라 문제의 크기가 일정 수만큼 줄어드는 경우
  ex) 팩토리얼
• 고정 비율 축소(Decrease by a constant factor)
• 문제의 크기가 일정한 비율로 줄어드는 경우
  ex) 이진 탐색
• 가변 크기 축소(Variable size decrease)
• 문제가 줄어든느 크기가 가변적인 경우
  ex) 유클리드 알고리즘 gcd(m,n) = gcd(n, m mod n)의 경우 반복에 따라 매번 줄어드는 크기가 일정하지 않음

삽입 정렬(Insertion Sort)

• 축소 정복 전략
• 손 안의 카드를 정렬하는 방법과 비슷함. 카드를 쥐고 새로운 카드를 한 장씩 받을 때마다 그 카드를 순서에 맞춰 끼워넣는 방식
• 앞부분부터 탐색할 경우 새로운 항목이 들어갈 위치를 확보하기 위해서 뒷부분들을 전부 한칸 씩 뒤로 밀어야 함.
  하지만 뒤부터 넣게 되면 비교를 하고 한칸씩 뒤로 밀어놓으면 되기 때문에 따로 뒷부분을 밀어야하는 문제가 발생하지 않는다.
• Python code

  def insertion_sort(A):
  n = len(A)
  for i in range(1,n):
      key = A[i]
      j = i-1
      while j>0 and A[j] > key:
          A[j+1] = A[j]
          j = j - 1
      A[j+1] = key

• 복잡도 분석
• 내부 루프의 반복 횟수가 입력 자료의 구성에 따라 달라짐
• 최선의 경우
• 리스트가 이미 오름차순으로 정렬되어 있는 경우
• O(n)
• 최악의 경우
• 리스트가 역으로 정렬되어 있는 경우
• O(n^2)
• 삽입 정렬의 장점
• 항목의 수가 작거나 이미 정렬 되어 있는 경우에 효율적으로 사용 될 수 있음
• 삽입 정렬의 단점
• 많은 항목을 이동해야 하므로 크기가 큰 경우에 효율적이지 않음

위상 정렬

• 방향 그래프 G = (V,E)일때, G에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점들을 순서대로 나열하는 것
• 방향 그래프가 위상 정렬이 가능하려면 사이클이 존재하지 않아야 함.
• 축소 정복 전략
1. 진입차수 0인 정점을 하나 선택한다.
2. 선택된 정점을 삭제하고 인접된 이웃 정점들의 진입차수를 갱신한다
3. 이 과정을 모든 점정이 삭제될 때까지 반복한다
• Python code

  mygraph = {"A" : {"C", "D"},
              "B" : {"D", "E"},
              "C" : {"D", "F"},
              "D" : {"F"},
              "E" : {"F"},
              "F" : {}
              }
  
  def topological_sort(graph):
      inDeg = {}
      for v in graph:
          inDeg[v] = 0
      for v in graph:
          for u in graph[v]:
              inDeg[u] += 1
  
      vlist = []
      for v in graph:
          if inDeg[v] == 0:
              vlist.append(v)
  
      while vlist:
          v = vlist.pop()
          print(v, end=' ')
  
          for u in graph[v]:
              inDeg[u] -= 1
              if inDeg[u]==0:
                  vlist.append(u)

• 복잡도 분석
• 정점의 수를 n, 간선의 개수를 e이라고 할 때 시간 복잡도는 O(n+e)이다
• 반복 할 때 마다 크기가 1씩 줄어드는 고정크기 축소전략의 예

이진 탐색(Binary Search)

• 탐색 작업이 정렬되지 않은 리스트라면 순차 탐색외에는 답이 없지만, 정렬되어 있다면 이진 탐색을 사용할 수 있다.
• 반복에 따라 문제의 크기가 절반으로 줄어드는 고정비율(1/2) 축소 정복 기법
• 축소 정복 전략
• 리스트의 중앙에 있는 항목을 먼저 조사한다. 만약 이 항목이 탐색키 보다 크다면 찾는 항목은 이 항목 왼쪽에 있고, 나머지 오른쪽 항목들은 검사할 필요가 없다. 반대로 그 항목이 탐색키보다 작다면 답은 오른쪽에 있고, 왼쪽은 검사할 필요가 없다. 따라서 각 단계 마다 검색해야 할 항목 수, 즉 문제의 크기가 반으로 줄어든다.
• Python code(순환구조)

  def binary_search(A,key, low, high):
  if(low <= high):
      mid = (low + high) // 2
      if key == A[mid]:
          return mid
      elif key < A[mid]:
          return binary_search(A, key, low, mid-1)
      else:
          return binary_search(A, key, mid+1, high)
  return -1

• Python code(반복구조)

  def binary_search_iter(A, key ,low, high):
  while(low <= high):
      mid = (low + high) // 2
      if key == A[mid]:
          return mid
      elif key > A[mid]:
          low = mid + 1
      else:
          high = mid - 1
  return -1

• 복잡도 분석
• 시간 복잡도는 O(log 2 n)이다
• 매우 효율적인 탐색 방법이지만 반드시 리스트가 정렬되어 있어야 함
• 데이터의 삽입이나 삭제가 빈번한 응용에는 적합하지 않음

거듭제곱 문제

• Python code

  def power(x, n):
  if n == 0 :
      return 1
  elif (n % 2) == 0 :
      return power(x*x, n // 2)
  else :
      return x * power(x*x, (n-1) // 2)

• 복잡도 분석
• 순환적으로 더 작은 부분 문제를 만들고, 이 문제가 바로 해결할 수 있을 만큼 작아질 때 (n=0)까지 순환적으로 호출한다.
• 이진 탐색에서와 같이 1/2의 고정 비율로 문제가 축소 된다.
• 시간 복잡도는 O(log 2 n)

k번째 작은 수 찾기

• 만약 k가 1이거나 n인 경우는 최솟값과 최댓값을 찾는 문제가 되고, n/2이라면 중앙 값을 찾는 문제가 된다.
• 축소 정복 전략
1. 리스트의 한 항목을 피봇(Pivot)으로 선택한다. 일반적으로 리스트의 맨 왼쪽 항목을 선택함
2. 리스트의 나머지 항목들을 모두 검사하여 피봇보다 작으면 피봇의 왼쪽으로 크면 오른쪽으로 옮긴다.
   이 방법을 통해 둘 중 한 부분은 고려하지 않아도 되게 된다.
• Python code

  def quick_select(A,left, right, k):
  pos = partition(A, left, right)
  
  if(pos + 1 == left + k):
      return A[pos]
  elif (pos + 1 > left + k):
      return quick_select(A, left, pos - 1, k)
  else :
      return quick_select(A, pos + 1, right, k - (pos + 1 - left))
  
  #Hoare Partition
  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(n)
• 최악의 경우
• 분할 할 때마다 부분 리스트의 한쪽은 항목이 없고 다른 한쪽에만 모든 항목이 들어가는 상황
• O(n^2)

축소 정복 기법의 추가적인 예

• 위조 동전 찾기(고정 비율 축소)
• 동일하게 생긴 n개의 동전과 양팔 저울이 있다. 동전들 중에는 하나는 가짜 동전이고 진짜보다 약간 가볍다.
• 시간 복잡도
• 동전을 1/2뭉치로 나눠가면서 가짜 동전을 찾을 경우 O(log 2 n)
• 동전을 1/3뭉치로 나눠가면서 가짜 동정르 찾을 경우 O(log 3 n)
• 보간 탐색(가변 크기 축소)
• 보간 탐색은 사전에서 단어를 찾을 때와 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법
• 이진 탐색에서 탐색 위치 middle은 (low + high)/2로 항상 리스트를 중간 위치에서 다음 탐색을 진행한다.
• 보간 탐색은 탐색 값과 위치는 비례한다는 가정을 사용하여 A[low]와 A[max]를 사용하여 Key가 A[low]에 가까운 만큼 인덱스도 low에 가깝도록 하고 A[high]에 가까운만큼 인덱스도 high에 가까운 위치에서 탐색하도록 가중치를 주는 방법이다.
• 보간 탐색은 가변 크기 축소의 대표적인 예이며, 시간 복잡도는 O(log 2 n)이다.
• 많은 데이터가 비교적 균등하게 분포 되어 있는 자료에서 더욱 효율적으로 사용 될 수 있다.