분할정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말한다.

분할정복의 사례를 보여주는 병합정렬이다.

분할정복은 직접 해결할 수 있을 정도로 간단한 문제가 될때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 냄.

폰노이만이 병합 정렬을 통해 분할 정복을 설명한 것은 1945 - 광복 년이었는데, 사실 문제를 축소해서 정복한다는 개념은 고대 까지 거슬러 올라간다.

그리스의 수학자 유클리드는 자신이 저술한 원론에서 문제를 분할해 풀이하는 최대 공약수 알고리즘을 정리했음. → 인류 최초의 알고리즘으로 일컬어진다.

• 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.
• 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
• 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

function F(x):
	if F(x)가 간단 then:
		return F(x)를 계산한 값
					----------------
									정복 1

	else:
		x 를 x1, x2로 분할
		F(x1)과 F(x2)를 호출
		return F(x1), F(x2)로 F(x)를 구한 값
		------ ------------
		조합 2      분할 3

83. 과반수 엘리먼트

과반수를 차지하는(절반을 초과하는) 엘리먼트를 출력하라.

Example 1: