[파이썬] Divide and Conquer

이 Divide and Conquer는 3단계로 나뉘어 진다.

 

1. Divide : 문제를 부분 문제로 나눈다.

 

2. Conquer : 각 부분 문제를 정복한다.

 

3. Combine : 부분 문제들의 솔루션을 합쳐서 기존 문제를 해결한다.

 

먼저 첫 번째 Divide

1 ~ 100의 합을 1 ~ 50, 51 ~ 100의 합으로 나눌 수 있다.

두 번째 이 두가지 나눈 것에대한 결과값을 Conquer하여

세 번째 combine해 문제를 풀면된다는 것이다.

 

예시)

def consecutive_sum(start, end):
    # base case
    if start == end:
        return start

    # recurcive case
    else:
        mid = (start + end) // 2
        return consecutive_sum(start, mid) + consecutive_sum(mid + 1, end)

이 함수는 start부터 end숫자까지의 합을 더하는 함수이다. 재귀함수로 보이지만 사실 

이 함수는 위에서 본 것과 같이 Divide, Conquer, Combine을 거쳤다.

base case는 계속 둘로 나누는 연산을 반복하니 결국에 start와 end가 같아지는 지점에 도달하면 그 값을 리턴하도록 한다.

그러면 recurcive case는 이러한 값이 리턴될 수 있도록 계속 반으로 쪼개어 둘을 더할 수 있도록 하면된다.

그러면 제대로된 결과값을 얻을 수 있다.