분할 정복(Divide and Conquer)

분할 정복(Divide and Conquer) 알고리즘 문제

분할 정복(Divide and Conquer)

• 먼저 분할하고 정렬하는 경우 - merge sort

• 먼저 정렬하고 분할하는 경우 - quick sort

• recursion(재귀)에서 중요한 것

  • base case(기저 조건)
  • 재귀할 때 문제의 사이즈(부분 문제, sub problem)를 줄여야 한다.

• 분할 정복(Divide and Conquer)도 문제의 사이즈를 절반으로 줄인다.

알고리즘 해결 전략 1권 p.190

• 쿼드 트리 뒤집기
• 모든 픽셀이 블랙인 경우 : b
• 모든 픽셀이 화이트인 경우 : w
• 모든 픽셀이 같은 색이 아니면 2 x 2로 4등분하여 x(0,0)(0,1)(1,0)(1,1)로 압축한다.
• 압축된 문자열이 주어질 때, 이를 뒤집은 압축 문자열을 생성하는 프로그램을 구현해보자.

  # 조건
  
  # 16 x 16
  n = 16
  compressed = "xxwwwbxwxwbbbwwxxxwwbbbwwwwbb"
  
  # Iterator class를 만들어쓰는 이유
  # 선형 자료 구조인지, 트리 구조인지 상관없이 반복하고 싶기 때문
  # 선형 자료 구조만 생각한다면 반복자는 필요가 없지만, 자료 구조에는 선형과 비선형이 모두 존재한다.
  class Iterator:
      def __init__(self, raw_string):
          self.string = raw_string
          self.iterator = -1
  
      def __iter__(self):
          return self
  
      def __next__(self):
          self.iterator += 1
          if self.iterator == len(self.string):
              raise StopIteration
          return self.string[self.iterator]
  
  # Iterator test code
  # it = Iterator(compressed)
  # print(next(it))
  # for ch in it:
  #     print(ch, end=" ")
  
  ret = [[None for _ in range(n)] for _ in range(n)]
  
  def decompress(it, y, x, size):
      # base case
      first = next(it)
      if first == 'b' or first == 'w':
          for i in range(size):
              for j in range(size):
                  ret[y+i][x+j] = first
  
      # 언제 decompress()를 호출할 것인가?
      # else라면 first = 'x'
      else:
          new_size = size//2
          decompress(it, y, x, new_size)
          decompress(it, y, x+new_size, new_size)
          decompress(it, y+new_size, x, new_size)
          decompress(it, y+new_size, x+new_size, new_size)
  
  def solve(it):
      # base case
      head = next(it)
      if head == 'b' or head == 'w':
          return head
  
      # head == 'x'인 경우
      else:
          c1 = solve(it)
          c2 = solve(it)
          c3 = solve(it)
          c4 = solve(it)
          return 'x' + c3 + c4 + c1 + c2
  
  # test code
  if __name__ == "__main__":
      # 뒤집기 전
      decompress(Iterator(compressed), 0, 0, n)
      print("< 뒤집기 전 >")
      for row in ret:
          for c in row:
              if c == 'b':
                  print('#', end = " ")
              else:
                  print('-', end = " ")
          print()
  
      print()
  
      # 뒤집기 후
      f = solve(Iterator(compressed))
      decompress(Iterator(f), 0, 0, n)
      print("< 뒤집기 후 >")
      for row in ret:
          for c in row:
              if c == 'b':
                  print('#', end = " ")
              else:
                  print('-', end = " ")
          print()

알고리즘 해결 전략 1권 p.195

• 울타리 잘라내기
• 너비가 1인 판자를 붙인 울타리가 있다.
• 판자의 높이가 주어지고 울타리의 일부를 잘라내려고 할 때
• 가장 넓이가 넓게 잘라내는 프로그램을 구현해보자.

  # 조건
  N = 7
  height = [7, 1, 5, 9, 6, 7, 3]
  
  # exhaustive solution
  def exhaustive():
      ret = 0
      for left in range(N):
          h = height[left]
          for right in range(left, N):
              h = min(h, height[right])
              temp = (right-left+1)*h
              ret = max(ret, temp)
      return ret
  
  # divide and conquer
  def divide_and_conquer(left, right):
      # base case
      if left == right:
          return height[left]
      
      mid = (left + right) // 2
      # max of A --> [left]
      lret = divide_and_conquer(left, mid)
      # max of A --> [right]
      rret = divide_and_conquer(mid + 1, right)
      ret = max(lret, rret)
      
      low = mid
      high = mid+1
      h = min(height[low], height[high])
      ret = max(ret, h*2)
      while low > left or high < right:
          if low > left and (high == right or height[low - 1] > height[high + 1]):
              low -= 1
              h = min(h, height[low])
          else:
              high += 1
              h = min(h, height[high])
              
          ret = max(ret, h*(high - low + 1))
  
      return ret
  
  # test code
  if __name__ == "__main__":
      print("완전 탐색(exhaustive)으로 해결한 경우")
      print(exhaustive())
  
      print()
  
      print("분할 정복(divide and conquer)으로 해결한 경우")
      print(divide_and_conquer(0, N-1))