[분할 정복]

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

직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다. 대표적인 분할 정복 알고리즘으로는 병합 정렬을 들 수 있다.

분할: 문제를 동일한 유형의 여러 하위 문제로 난눈다.

정복: 가장 작은 단위 하위 문제를 해결하여 정복한다.

조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

분할 정복의 기본 틀

function F(x):
	if F(x)가 간단 then:
		return F(x)를 계산한 값 (정복)
	else:
		x를 x1, x2로 분할
		F(x1)과 F(x2)를 호출
		return F(x1), F(x2)로 F(x)를 구현한 값 (조합, 분할)

1)과반수 엘리먼트 -하, 분할 정복

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

https://leetcode.com/problems/majority-element/

2. 괄호를 삽입하는 여러 가지 방법 - 중, 분할 정복

숫자와 연산자를 입력받아 가능한 모든 조합의 결과를 출력하라.

https://leetcode.com/problems/different-ways-to-add-parentheses/

[append() vs extend()]

a = [1,2,3]
b = [4,5]
a.append(b)
print(a)
>>[1,2,3, [4,5]]

a = [1,2,3]
b = [4,5]
a.extend(b)
print(a)
>>[1,2,3,4,5]