[Divide and Conquer] 1부터 n까지의 합

Divide and Conquer를 이용해서 1부터 n까지 더하는 예시를 보았는데요. 코드로 한 번 구현해 봅시다.

우리가 작성할 함수 consecutive_sum은 두 개의 정수 인풋 start와 end를 받고, start부터 end까지의 합을 리턴합니다. end는 start보다 크다고 가정합니다.

 

consecurive_sum.py

def consecutive_sum(start, end):
    # 여기에 코드를 작성하세요
    # base case
    if start == end:
        return start
    
    # 부분 문제를 반으로 나눠주기 위해서 문제의 정중앙을 정의한다.(Divide)
    mid = (start + end) // 2
    
    # 각 부분을 재귀적으로 풀고(conquer), 부분문제의 답을 서로 더한다.
    return consecutive_sum(start, mid) + consecutive_sum(mid+1, end)
        
    

# 테스트 코드
print(consecutive_sum(1, 10))
print(consecutive_sum(1, 100))
print(consecutive_sum(1, 253))
print(consecutive_sum(1, 388))

 

해결 과정

basecase: start와 end가 같을때, start 리턴

recursive case:

1부터 100100까지의 합을 구한다고 가정할때,

1. Divide: 11부터 5050까지의 합을 구하는 부분 문제와, 5151부터 100100까지의 합을 구하는 부분 문제로 나눈다.
2. Conquer: 11부터 5050까지의 합을 구하고, 5151부터 100100까지의 합을 구한다.
3. Combine: 11부터 5050까지의 합과 5151부터 100100까지의 합을 더한다.