원문제를 같은 형태의 더 작은 문제로 나눈다.
DIVIDE AND CONQUER
분할 정복은 문제를 쪼갠 뒤 병합 계약을 지켜 정답을 만든다
핵심은 재귀 호출 자체가 아니라 부분 문제의 의미와 병합 결과의 정확성을 끝까지 유지하는 것이다.
더 나누지 않아도 답을 알 수 있는 조건을 둔다.
각 부분 문제의 반환 의미를 동일하게 유지한다.
부분 답을 전체 답으로 합치는 규칙을 검증한다.
예시merge sort
위험병합 누락
검증작은 입력 추적