분할 정복으로 리스트의 합 구하기 해설

주어진 정수 리스트의 모든 요소들의 합을 분할 정복(divide and conquer) 방법으로 계산하는 함수를 작성합니다.

이 방법은 재귀 함수를 사용하여 구현됩니다.

1. 기본 함수 solution:

   • 사용자에게 입력 받은 리스트와 리스트의 시작 및 끝 인덱스를 recursive_sum 함수에 전달합니다.

2. 재귀 함수 recursive_sum:

   • Base Case 처리:

     • 리스트가 비어있을 경우 (start > end), 0을 반환합니다.

     • 리스트에 하나의 요소만 있을 경우 (start == end), 해당 요소를 반환합니다.

   • 분할 과정:

     • 리스트를 중간 지점에서 두 부분으로 나눕니다.

   • 정복 과정:

     • 각 부분의 합을 재귀적으로 계산합니다.

   • 결합 과정:

     • 계산된 두 부분의 합을 합산하여 반환합니다.

Copy
def solution(numbers):
    # 기본 함수
    return recursive_sum(numbers, 0, len(numbers) - 1)

def recursive_sum(numbers, start, end):
    # Base case 처리
    if start > end:
        return 0
    if start == end:
        return numbers[start]

    # 분할 과정
    mid = (start + end) // 2

    # 정복 과정
    left_sum = recursive_sum(numbers, start, mid)
    right_sum = recursive_sum(numbers, mid + 1, end)

    # 결합 과정
    return left_sum + right_sum

Copy
print(solution([1, 2, 3, 4, 5]))  # 출력: 15