[PS] 분할정복

분할정복의 시간복잡도는 NlogN이다. (단계 별 문제 개수 (N//2^K) X 해당 단계에서 쪼개는/병합하는 시간(2^K) X 단계 개수(크기가 이진탐색 수준으로 줄기 때문에 logN)) 
이것을 밑으로 내려가면서 쪼갤 때 / 위로 올라오면서 병합할 때 2번해서 어차피 2 NlogN이므로 시간복잡도는 그냥 NlogN이다. (DP테이블은 문제 종류가 M이라고 하면 O(NM)이라 더 효과적인 것을 확인할 수 있음)

★DP와 다른 점
부분 문제가 서로 중복되지 않는다. 
위 사항 덕분에 Memoization이 필요하지 않다. 굳이 내가 알아낸 데이터를 저장하지 않는다.

★이분탐색트리 또는 세그먼트 트리와 다른 점
이분탐색/세그먼트는 일단 아는 노드를 쭉 나열해 두고 둘씩 짝지어서 위로 올라가며 판단하는 과정을 거친다.
하지만 분할정복은 내가 알고싶은 큰 문제를 찢어서 작은문제로 나눈 후 그 작은 문제들로 큰 문제를 해결해 나간다.
(이 점은 DP top-down와 비슷하다고 생각할 수 있음)

간단한 로직은 다음과 같다.

def div_conquer():
    #가장 밑 분할 노드 도착했을 때 return

    #그게 아니라면,
    #분할해서 간 결과값 1
    a=div_conquer( )
    #분할해서 간 결과값 2
    b=div_conquer( )
    #그걸 이용해 합치든가 뭘 해서 암튼 정복
    c=a+b

간단한 그림은 이렇게 나타낼 수 있다. 현재 그림처럼 배열에서 계속해서 이분적으로 쪼개버림으로써, 특정 범위를 신경쓰지 않아버리는 실수를 주의하자.