[알고리즘 일기] 11. 1부터 n까지의 합

 

 

문제 11. (2021-05-11)

1부터 n까지의 합

분할 정복 방식을 사용하여 1부터 n까지 더하는 함수를 작성하시오.

 

 

주의사항

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

 

 

❧ 테스트 셋

def consecutive_sum(start, end):
    #code

#Test
print(consecutive_sum(1, 10))
print(consecutive_sum(1, 100))
print(consecutive_sum(1, 253))
print(consecutive_sum(1, 388))

 

❧ 출력 예시

55
5050
32131
75466

 

---

❧ 정답

def consecutive_sum(start, end):
    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))

 

1️⃣ Divide : 주어진 문제를 반으로 나누어 두 개의 부분 문제로 나눈다.

2️⃣ Conquer : 두 부분 문제를 재귀적으로 구한다.

3️⃣ Combine : 계산한 두 부분 문제의 답을 더한다. 두 리스트를 하나의 정렬된 리스트로 합병한다.