divide and conquer

분할 정복은 같은 반환 계약을 병합한다

하위 호출이 무엇을 돌려주는지 먼저 고정해야, 나누기와 합치기가 한 문제의 해로 이어진다.

원문제 기저 정렬 반환

병합 정렬로 보는 반환 계약

5 1 3 2
입력 구간 정렬된 배열을 반환해야 한다
51
왼쪽 하위 문제 반환 형식은 원문제와 같다
32
오른쪽 하위 문제 반환 형식은 원문제와 같다
5
기저 이미 정렬됨
1
기저 이미 정렬됨
3
기저 이미 정렬됨
2
기저 이미 정렬됨
15
병합 결과 정렬된 배열 반환
23
병합 결과 정렬된 배열 반환
1 2 3 5
최종 반환 상위 문제도 같은 계약을 만족한다
분할같은 형태의 더 작은 입력으로 나눈다.
정복각 하위 호출은 같은 반환 계약을 지킨다.
병합두 반환값을 합쳐 상위 계약을 만족시킨다.
질문 병합 정렬의 답 빠지면 생기는 문제
하위 호출은 무엇을 반환하나 정렬된 배열 병합 조건이 모호해진다
기저는 계약을 만족하나 길이 1 배열은 이미 정렬 재귀가 멈춰도 답이 아닐 수 있다
병합이 계약을 보존하나 두 정렬 배열을 앞에서부터 비교 상위 반환값의 의미가 깨진다
핵심: 분할 정복의 코드는 “나누기”보다 “하위 반환값을 어떤 규칙으로 다시 계약에 맞추는가”에서 결정된다.