[알고리즘] 분할정보(Divide and Conquer) 알고리즘

분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 알고리즘.

개념은 큰 문제를 점차 작은 문제로 나누어 가면서 풀 수 있는 최소단위 문제로 해결하고, 이를 다시 합쳐서 해결하는 것

절차

1) 분할 (Divide)

- 2개 이상의 문제들로 분리. 더이상 분할할 수 없을 때까지 동일한 여러 하위 문제로 나눔,

2) 정복 (Conquer)

- 나누어진 작은 문제를 해결. 

3) 조합 (Combine)

- 해결한 문제들을 합침. 하위 문제의 결과를 원래 문제에 대한 결과로 조합(합침)

 

# 1~n까지의 합
def func_sum(s, e):   # start, end
    
    if s == e:
        return s                                      # 정보(해결): 가장 작은 문제의 해결 리턴
    
    mid = (s + e) // 2                                 # 분할 조건 : 어떤 조건으로 분할 하는가?
    
    # *분할 : 2개 이상의 작은 문제로 분할(2개의 합수로 분리(재귀). *조합: 작은 문제해결 결과를 조합(합침. + 로 결과 합침)
    return func_sum(s, mid) + func_sum(mid + 1, e)

    
print(func_sum(1, 100))