#Divide#Conquer#combine#1부터 n까지 더하는 문제

문제를 부분으로 나눠서(Divide), 그것들의 해답을 구한다(Conquer). 그 부분의 답들을 적절하게 합쳐서(Combine) 전체의 답을 구한다. 

 

먼저 Divide & Conquer의 경우에도 1) 자신이 정의한 함수를 써도 되지 않아도 되는 base부분과 함수를 적용해 2) recursive 되게 풀어야 하는 부분 두 가지 경우를 나누어서 생각해야 한다. 

 

1부터 n까지 더하는 문제를 생각해보자. 가장 쉽게는 for문을 사용해서 1부터 n까지의 값을 차례대로 호출하여 더해가는( += data)를 생각해볼 수도 있으나, Divide & Conquer하여 푼다고 생각해보자.

어떤 경우에 반복적인 함수를 써도 되지 않을까? 더 이상 부분으로 쪼개어 나누어서 풀 수 없는 경우

즉, start 부분과 end부분이 같은 경우다. 그래서 이를 base로 표현하고

다음으로 어떤 부분을 반복적으로 연산해야 하는가? 가장 쉽게는 1~n까지의 수를 반으로 계속해서 나누는 경우를 생각해볼 수 있다. 여기서 핵심은 반으로 나눈다는 부분에 있으며 mid = (start+end)//2로 표현한다. 

이후 mid되는 지점을 중심으로 전부분 후부분으로 나누어서 우리가 정의한 repetitive_sum의 함수 인자 값으로 들어가게 만든다.

def repetitive_sum (start, end):
	if start == end
    	return start
    
    else: 
    	mid = (start + end) //2
        return repetitive_sum(start, mid) + repetitive_sum(mid+1, end)