divide and conquer에 대해

분할 정복을 이용하는 문제 특징

def divde_and_conquer(total):
	if {base condition}:
    	return v_base
        
        
    v_1 = divide_and_conquer(left_half)
    v_2 = divide_and_conquer(right_half)
    
    
    
    # 여기가 주로 구현해야하는 부분
    # O(n)으로 left_half + right_half 에서 원하는 값을 구하는 알고리즘을 구현해야 한다.
    def function(left_half, right_half):
    	...
        ...
        return v_3
        
    v_3 = function(left_half + right_half)
    
    
    
    return min(v1, v2, v3) or max(v1, v2, v3)
    

결국 overall time complexity 는 O(nlogn)인 경우가 많다.