Divide and Conquer(분할 정복)

Divide and Conquer(분할 정복) 방법

• 복잡하거나 큰 문제를 여러 개로 나눠서 푸는 방법이다.
  • 특징 : 병렬적으로 문제를 해결할 수 있다.(하지만, 문제를 해결하기위해 문제해결함수가 재귀적으로 호출될 수 있으므로 메모리가 추가적으로 사용될 수 있다.)
• 재귀호출은 같은 함수코드를 재호출하는 것(같은 함수코드 사용)
• 분할정복은 비슷한 작업을 재진행하는 것(같은 함수코드는 아닐 수 있음)

• 분할정복의 과정
  • 본 문제를 서브문제로 분할(divide)
  • 서브문제의 답을 구한 경우, 해당 답을 본 문제에 대한 답이 되도록 병합함(Merge)
  • 문제를 분할할 수 없거나, 할 필요없는 경우에 대한 답을 구함(base case, 기본 케이스)
• 분할정복의 조건
  • 본 문제를 서브문제로 분할할 수 있는가?(Divide)
  • 서브문제의 답을 병합(또는 조합)하여 본 문제의 답을 구하는 것이 효율적인가?(Merge, Conquer)

# 재귀: 1부터 10까지의 합
def func(num):
    if num < 1:
        return 0
    else:
        return num + func(num-1)

func(10)

# 분할정복: 1부터 10까지의 합
def func(num):
    if num == 1:
        return 1
    if num % 2 == 1:
        return func(num - 1) + num
    else:
        return func(num / 2) * 2 + (num / 2) * (num / 2)

func(10)