[알고리즘] [Divide and Conquer 분할 정복] 1부터 N까지 더하는 문제를 분할 정복으로 구현하기

분할정복이란 문제를 모두 부분 문제로 나눠서 해결하는 알고리즘이다.

문제들이 충분히 나누어졌다고 생각할 때까지 문제를 작게 나눈다.

 

분할 정복의 3단계

1. Divide: 주어진 문제를 반으로 나누어 두 개의 부분 문제로 나누기
2. Conquer: 두 부분 문제를 재귀적으로 구하기
3. Combine: 계산한 두 부분 문제의 답을 더하기

def consecutive_sum(start, end):
    # n과 n이 같은 경우       
    if end == start:
        return start

    # 부분 문제를 반으로 나누기 위해 문제의 정중앙을 정의
    mid = (start + end) // 2

    # 각 부분 문제를 재귀적으로 풀고(Conquer), 부분 문제의 답을 서로 더함(Combine)
    return consecutive_sum(start, mid) + consecutive_sum(mid + 1, end)

# 테스트 코드
print(consecutive_sum(1, 100))

 

ex. 1부터 100까지 합을 구한다고 가정

1. Divide: 1~50까지의 합을 구하는 부분 문제, 51~100까지의 합을 구하는 부분 문제로 나누기
2. Conquer: 1~50까지의 합을 구하고, 51~100까지의 합 구하기 (각 부분문제 해결)
3. Combine: 두 계산 결과를 합하기