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