Divide and Conquer

문제를 풀기에 너무 크다고 가정을 했을때 문제를 나누어서 푸는것을 말한다.

기존의 문제를 나누어 부분 문제로 나누어 각 부분문제를 풀어 기존의 문제를 해결하는것을 말함.

 

 * Divide : 문제를 부분 문제로 나눔

   Conquer : 각 부분 문제를 정복

   Combine : 부분 문제들의 해결책을 합쳐 기존 문제를 해결

 

구성요소

1. Divide

2. Conquer

   - 해당 단계에서 문제가 너무 크다면 위와 같은 과정을 반복

   1. Divide

   2. Conquer

       1. Divide

       2. Conquer

       3. Combine

             .....

   3. Combine

3. Combine

 

def consecutive_sum(start, end):        
    if end == start:
        return start

    # 문제를 부분문제로 나눈다
    mid = (start + end) // 2

    # 각 부분 문제를 재귀적으로 풀고(Conquer), 부분 문제의 답을 서로 더한다(Combine).
    return consecutive_sum(start, mid) + consecutive_sum(mid + 1, end)