분할 정복[Divide and Conquer] 정리

분할 정복[Divide and Conquer]

 

문제 -> 부분 문제로 나누어서 각 부분문제를 풀고 그 솔루션을 사용하여 문제를 해결

 

분할 정복의 3단계 

1. Divide : 문제를 부분 문제로 나눈다

2. Conquer: 부분 문제를 푼다 -> 정복한다 

3. Combine: 부분 문제들의 솔루션을 합쳐서 기존 문제를 해결

 

Conquer의 문제가 크면 이 문제도 분할 정복을 여러 번 거쳐 풀 수 있다

 

ex) 1 ~ n까지 더하기

 

def consecutive_sum(start, end):
    if start == end:
        return start
    middle = (start+end)//2
    return consecutive_sum(start,middle)+consecutive_sum(middle+1,end)

 

분할 정복은 보통 재귀 함수로 구현하기 때문에 재귀 함수를 사용하여 부분 문제를 풀고 return에 값을 서로 더하여 해결