[알고리즘] Divide and Conquer 분할정복 : 1부터 n까지의합

선행 : 재귀개념

분할정복 : 부분문제를 풀고, 그 솔루션을 활용하여 문제를 해결한다.

1. Divide : 인풋 x를 x1과 x2로 나눈다.

2. Conquer : f(x1) ,f(x2) -> divide/conquer/combine로 나눠질 수 있음

3. Combine : f(x) 계산

 

실습설명

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

 

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

 

답안

def consecutive_sum(start, end):
    # 여기에 코드를 작성하세요
    if start ==end:
        return start
    else:
        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))