Python - 분할 정복 (Divide and Conquer)

- 분할 정복

다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말한다.
분할 정복은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 
그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어낸다.

 

- 대표적인 분할 정복 알고리즘으로는 병합 정렬을 들 수 있다.

아래 그림은 병합 정렬을 이용한 분할 정복의 원리를 잘 보여준다.

파이썬 알고리즘 인터뷰 그림 22-2

파이썬 알고리즘 인터뷰 그림 22-1

 

* 정리

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)를 구한 값