[파이썬] 1부터 n까지의 합 - 분할 정복 ★

실습 설명

Divide and Conquer를 이용해서 1부터  n까지 더하는 과정을 코드로 한 번 구현해 봅시다.

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

실습 결과

def consecutive_sum(start, end):
    # base case
    if start == end:
        return start
        
    # 분할
    mid = (start + end) // 2
    
    # 정복
    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))

55
5050
32131
75466