Divide and conquer

분할정복(Divide and Conquer)

1. 문제를 sub-problem들로 분할(divide)
2. atomic한 레벨까지 분할한다.
3. atomic한 레벨에서 문제를 푼다(conquer).
4. atomic한 해들을 합쳐서 sub-problem들을 풀고, 위로 올라가며 전체 문제들을 푼다.

분할정복 알고리즘의 성질

• 전체 문제가 sub-problem들의 집합으로 표현될 수 있다.
• 전체 문제와 sub-problem들의 구조가 같은 경우, 해를 재귀적으로 정의 해서 풀 수 있다
• atomic 단계가 어떤 단계인지 파악 해야한다(recursion base condition).

분할정복 branching factor

최초 문제를 atomic solution들의 n개 집합이라고 가정하자. 그리고 각 레벨에서 b개의 sub-problem들로 분기 된다고 하자. 이 경우 leaf의 개수, 즉 atomic problem들의 개수는 아래와 같다.

$width = a^{\log_b{n}} = n^{\log_b{a}}$

---

분할정복과 재귀함수

분할정복의 해는 재귀함수로 표현 되는 경우가 많다. 왜 그럴까? 슈도코드를 보자.

function solution(this condition){
	if (this condition == base case condition) {
    	base case instructions...
		return base case solution;
	}
    non-base case condition instructions...
    return solution(next condition); 
}

이렇게 표현된다. 재귀함수는 자기자신으로 정의된다. 즉, 파라메터를 제외하고는 형태와 구조가 같다. 그리고 파라메터는 동일한 형태와 구조를 가진 함수의 특정 단계에서의 인스턴스를 결정하게 된다. (특정 sub-problem의 해가 된다.)

파라메터를 넘겨줌으로써 각 단계의 문제와 매핑 되는 해가 정의 되고, 해당 함수로 각 단계에 대한 해를 구할 수 있게 된다. 재귀는 가장 atomic한 단계의 기저조건까지 이 함수를 호출한 뒤, 기저 단계의 atmoic한 문제를 풀고, 그걸 윗 레벨로 넘겨서 같은 형태의 문제를 풀어나가는 방식으로 동작하게 된다.

결과적으로 코드상으로 봤을 때 재귀함수는 동일한 형태로 모든 sub-level에 매핑 되는 해가 된다. 그리고 이 각각의 sub-level을 어떻게 처리하느냐에 따라 backtracking, dynamic programming 알고리즘으로 변주를 줄 수 있는 것 같다.

...너무 중언부언한 거 같아서 나중에 정리가 필요할 거 같음.

---

REFERENCE

[1] https://www.youtube.com/watch?v=3E5jOehE44k