분할 정복(Divide and Conquer)

목차

분할 정복(Divide and Conquer)

• 분할 정복은 큰 문제를 독립적인 작은 문제들로 나누어 해결합니다. 각각의 작은 문제들은 독립적으로 해결되며, 결합 단계에서 이러한 작은 문제들의 해답을 결합하여 큰 문제의 해답을 얻습니다.
  • 따라서 재귀형태로 구현하는 경우가 많습니다.
• 대표적인 예시로는 병합 정렬(merge sort), 이분 탐색(binary search) ,거듭제곱 연산(a^n)등이 있습니다.
  • 병합 정렬
    • 
  • 이분탐색
    • 
  • 거듭제곱 연산
    • 기본적인 거듭제곱 연산의 시간복잡도는 O(n)입니다. 이는 'a'를 'n'번 곱하는 것을 의미합니다. 분할 정복을 사용하면 이를 O(log n)으로 줄일 수 있습니다.
    • 
   

분할정복과 Top-Down 방식의 DP와 차이점

• 분할정복은 DP의 Top-Down 방식과 유사합니다. 둘 다 작은 문제로 쪼개서 해결하기 때문입니다. 
• 그럼 둘 사이에는 어떤 차이점이 존재할까요?
  • 분할정복은 문제를 분할했을 때 겹치는 부분 문제가 없을 때 효율적입니다.
  • 반대로 DP는 겹치는 문제가 발생했을때 사용합니다. DP는 중복되는 문제를 메모이제이션(memoization)기법을 통해 기록해두었다가 시간절약을 할 수 있습니다. 하지만 굳이 분할할때 겹치는 문제가 없을 경우면, 이러한 방법은 메모리를 낭비하는 방법이 됩니다.
  • 예를 들어, 거듭제곱의 경우는 중복되는 연산이 없기때문에 분할정복이 효율적이지만, 피보나치 수열처럼 분할을 하고 연산하는 과정에서 중복되는 연산이 많을 경우는 DP 방식이 효율적입니다.
• 분할 정복(거듭제곱 예시) vs Top-Down DP(피보나치 수 예시)
  • 거듭제곱 (겹치는 것이 없음)

    •             a^n
               /        \
          a^(n/2)       a^(n/2)
         /      \       /      \
      a^(n/4) a^(n/4) a^(n/4) a^(n/4)  
      ...  ...  ...

  • 피보나치 수 (겹치는 것이 다수 존재)
    • 
• 정리하면, Top-Down 방식으로 문제를 접근할 수 있을때, 중복되는 연산이 존재한다면 DP, 아닐경우 분할정복으로 해결하면됩니다.
  
  • 저는 Top-Down 방식의 DP 보다는 Bottom-Up 방식의 DP로 코드를 작성하는 것을 선호하기 때문에 Top-Down 방식의 DP일 경우 Bottom-Up 방식의 DP로 변경하여 문제를 해결합니다.

예시

• [백준 10830] 행렬 제곱
  • 행렬은 곱셈에 있어 교환 법칙은 성립하지 않지만, 곱셈의 결합법칙은 성립합니다.
  • 즉, (AB)C = A(BC) 인데 이럴 경우 뒤에 먼저 계산해주더라도 문제가 없습니다.
  • 결국 A^B 를 A^(B/2)로 나누어 나가면서 거듭제곱의 분할 정복방식으로 문제를 풀어나가면 됩니다.
  • 코드

    • import sys
      
      input = sys.stdin.readline
      
      n, b = map(int, input().split())
      
      arr = [list(map(int, input().split())) for _ in range(n)]
      
      
      def matrix_dot(a, b):
          n_row = len(a)
          n_column = len(b[0])
      
          mid = len(a[0])
      
          ans_arr = [[0 for _ in range(n_column)] for _ in range(n_row)]
      
          for row in range(n_row):
              for column in range(n_column):
                  value = 0
                  for i in range(mid):
                      value += ((a[row][i] % 1000) * (b[i][column] % 1000)) % 1000
                  ans_arr[row][column] = value % 1000
      
          return ans_arr
      
      
      def matrix_square(arr, n):
          if n == 1:
              return arr
      
          if n % 2 == 1:
              temp = matrix_square(arr, n // 2)
              return matrix_dot(arr, matrix_dot(temp, temp))
          else:
              temp = matrix_square(arr, n // 2)
              return matrix_dot(temp, temp)
      
      
      answer = matrix_square(arr, b)
      for i in range(n):
          print(*[item % 1000 for item in answer[i]])

• [백준 1725] 히스토그램
  • 이 문제를 만약 분할정복을 사용하지 않는다면, N개의 히스토그램 칸에 대해서 모든 히스토그램 칸에 대해서 시작지점과 끝지점을 선택해줘야합니다.
    • 이렇게될경우 결국 시간복잡도는 O(N^2)이 될것입니다. N의 최댓값이 100000이기 때문에 O(N^2)이라면 10000000000 으로 100억이 되게 됩니다.
    • 따라서 완전 탐색으로는 해결할 수 없는 문제입니다.
  • N이 100000일경우 O(nlog n)까지 허용됩니다. 모든 히스토그램 칸에 대해서 왼쪽,오른쪽으로 나눠서 각 mid를 포함하는 가장 큰 직사각형의 넓이를 구해보는 방법을 적용해볼 수 있습니다.
    • 각 히스토그램 봉(mid)을 포함하는 가장 큰 직사각형 넓이를 구하면 됩니다.
    • 이렇게 할 경우 체크를 하지 못하는 경우가 있는거 아니야? 할 수 있습니다. 하지만 가운데봉을 포함하면서 가장 큰 직사각형을 모두 체크하기 때문에 포함되지 않는 경우를 생각해보려고 하더라도 이미 아래 과정에서 모두 포함되어져 있을 것입니다.
    • 
  • 참고 : 분할정복보다 스택으로 푸는 방식이 O(N)으로 시간효율성이 더 높습니다. 
    • 스택 문제 풀이 : https://comdon-ai.tistory.com/32
  • 코드
    

    • import sys
      
      sys.setrecursionlimit(int(1e6))
      input = sys.stdin.readline
      
      n = int(input())
      
      arr = [int(input()) for _ in range(n)]
      
      
      def find(left, right):
          global max_value
      
          if left > right:
              return
      
          mid = (left + right) // 2
      
          left_idx = mid
          right_idx = mid
          min_height = arr[mid]
          while True:
              max_value = max(max_value, min_height * (right_idx - left_idx + 1))
      
              if left_idx - 1 >= left and right_idx + 1 <= right:
                  if arr[left_idx - 1] >= arr[right_idx + 1]:
                      left_idx -= 1
                      min_height = min(min_height, arr[left_idx])
                  else:
                      right_idx += 1
                      min_height = min(min_height, arr[right_idx])
      
              elif left_idx - 1 >= left and right_idx + 1 > right:
                  left_idx -= 1
                  min_height = min(min_height, arr[left_idx])
      
              elif left_idx - 1 < left and right_idx + 1 <= right:
                  right_idx += 1
                  min_height = min(min_height, arr[right_idx])
      
              else:
                  break
      
          find(left, mid - 1)
          find(mid + 1, right)
      
      
      max_value = 0
      find(0, n - 1)
      print(max_value)