분할 정복 알고리즘 (Python Algorithm interview 22장)

분할정복

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

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

  

분할 정복의 순서

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

분할 정복 수도 코드

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)를 구한값
		------ ------------------
		 [조합]       [분할]

• 작은 단위로 분할해서 정복 후 정답을 조합해 나가는 방식이다

분할정복의 장점

• 문제를 나눠서 풀어 어려운 문제를 해결할 수 있다
• 병렬적으로 문제를 해결할 수 있는 장점이 있다

분할정복의 단점

• 함수를 재귀적으로 호출하기 때문에 함수 호출로 인한 오버헤드가 발생한다
• 스택에 다양한 데이터를 보관하고 있어야 하기때문에 스택 오버플로우가 발생하거나 과도한 메모리를 사용하게 된다

분할 정복의 예시

• 병합 정렬
• 퀵 정렬