[Algorithm] Python 1부터 n까지의 합

* 본 문제는 코드잇에서 제공하는 문제이므로 자세한 문제 내용은 적지 않겠습니다.

 

[문제]

1부터 n까지의 합을 divide and conquer(분할정복)으로 풀기

 

[해설]

consecutive_sum(1, 10)

1을 start, 10을 end 로 생각했을 때, 두 case를 base case로 만들 수 있는 경우를 생각한다.

재귀함수를 생각했을 때, start값과 end값이 같게되면, 더 이상 연산이 필요 없어지므로, 그대로 start 또는 end값을 return 하면되는 base case가 충족된다.

부분문제를 반으로 나누어졌을 때, recursive하게 풀어 그 return 값들을 서로 더하며 답을 찾아간다.

 

[코드]

def consecutive_sum(start, end):
    if start == end: # 더 이상의 부분문제가 나눌 것이 없을 때 하나만 남은걸 return
        return start

    center = (start + end) // 2
    return consecutive_sum(start, center) + consecutive_sum(center + 1, end)
print(consecutive_sum(1, 10))
print(consecutive_sum(1, 100))
print(consecutive_sum(1, 253))
print(consecutive_sum(1, 388))