본문으로 건너뛰기
실습하기

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

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

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


함수 구현​

  1. 기본 함수 solution:

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

  2. 재귀 함수 recursive_sum:

    • Base Case 처리:

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

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

    • 분할 과정:

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

    • 정복 과정:

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

    • 결합 과정:

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

모범 답안
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

사용 예시​

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

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!