분할 & 정복 (Divide and Conquer)

 * 분할 & 정복 (Divide and Conquer)

큰 문제를 여러 작은 부분 문제로 나누고
각 부분 문제를 해결한 후
해결책을 결합하여 전체 문제를 해결하는 방식

문제 해결 순서는 
 1. 분할 방법 결정
 2. 기저 조건 설정
 3. 하위 문제 해결
 4. 하위 정답 종합


기저 조건 (Base Condition)
더 이상 분할이 불필요한 조건


하위 문제 해결에서 재귀 혹은 스택 사용


분할 함수와 확인 함수를 따로 둔다
 1. divide()
 2. check()

분할 함수에서 확인 함수를 호출하여 부분 문제의 조건 만족 여부에 따라 더 분할할지, 전체 정답에 반영할지 결정하는 방식

divide() : 문제를 분할하고 재귀적으로 호출

check() : 현재 범위가 조건을 만족하는지 확인


배열을 분할할 때 새로운 배열을 만들 필요는 없다
시작 인덱스와 크기를 새로 설정하여 재귀 혹은 스택에 넘기면 편하다

..~~~~..