[알고리즘] 문제5 - Divide and Conquer (분할 정복)

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다.

 

분할 정복(Divide and Conquer) : 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘

분할 정복 3단계

- 1. Divide(분할)

- 2. Conquer(정복 == 풀기)

- 3. Combine(합치기)

 

---

1 . 1부터 n까지의 합 구하기

 

 조건 

-함수명 : consecutive_sum

-매개변수명 : start, end (end > start)

- start부터 end까지의 합 리턴

---

풀이

def consecutive_sum(start, end):
    # base case        
    if end == start:
        return start

    # 부분 문제를 반으로 나눠주기 위해서 문제의 정중앙을 정의한다 (Divide)
    mid = (start + end) // 2

    # 각 부분 문제를 재귀적으로 풀고(Conquer), 부분 문제의 답을 서로 더한다(Combine).
    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))