분할 정복 병합 계약
문제를 쪼개기 전에 하위 문제가 무엇을 보장하고, 두 결과를 어떻게 합칠지 문장으로 고정합니다.
같은 형태로 나누기
배열 반쪽, 구간 절반처럼 원래 문제와 같은 의미의 하위 문제를 만듭니다.
최소 입력 처리
길이 0 또는 1처럼 직접 답을 알 수 있는 구간을 둡니다.
부분해 병합
정렬성, 최대합, 최소거리 같은 보장 조건이 유지되어야 합니다.
불변식 확인
병합 전제와 결과 성질이 어긋나면 전체 정답이 깨집니다.
문제를 쪼개기 전에 하위 문제가 무엇을 보장하고, 두 결과를 어떻게 합칠지 문장으로 고정합니다.
배열 반쪽, 구간 절반처럼 원래 문제와 같은 의미의 하위 문제를 만듭니다.
길이 0 또는 1처럼 직접 답을 알 수 있는 구간을 둡니다.
정렬성, 최대합, 최소거리 같은 보장 조건이 유지되어야 합니다.
병합 전제와 결과 성질이 어긋나면 전체 정답이 깨집니다.