분할 정복과 거듭 제곱 알고리즘

 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 어려운 문제를 작은 문제로 분할하여 해결하는 알고리즘을 의미한다. 재귀함수(Recursive function)를 통해서 자연스럽게 구사되는  데 대략적으로 이렇게 구성된다.

Recursive_Function(input){
	if(input is simple){
    	return answer; 
    }
    else{
    	partitial_Answer_1 = Recursive_Function(part_of_input_1);
        partitial_Answer_2 = Recursive_Function(part_of_input_2);
        partitial_Answer_3 = Recursive_Function(part_of_input_3);
                                  ...
        partitial_Answer_n = Recursive_Function(part_of_input_n);
        
        return combination_of_partitial_answer(partitial_Answer_1, 
        	partitial_Answer_2, partitial_Answer_3, ... partitial_Answer_n);
    }
}

 분할 정복을 응용한 예로 거듭제곱 알고리즘을 꼽을 수 있을 것 같다. 어떤 수 a에 대해서 N 승을 구한다고 가정하자. 단순하게 반복문을 이용해서도 답을 구할 수 있을 것이다. 다만 지수가 커짐에 따라서 필요한 연산의 수도 크게 증가한다.

Big-O로 표기하자면 O(N) 이다.

 분할 정복알고리즘을 사용하면 지수의 크기가 커져도 처리 연산의 수가 상대적으로 덜 증가하는 효과를 누릴 수 있다. 간단하게 말로 설명하자면 a^N을 a^(N/2) * a^(N/2) 꼴로 분할해 나가면 분할 단계마다 연산량이 절반으로 줄어드는 효과를 누리는 것이다. Big-O로 표기하자면 O(logN)이다.

 아래의 코드는 각각 단순 반복문, 재귀(단순 재귀, 다이나믹 프로그래밍), 분할 정복 알고리즘을 이용하여 입력에 대한 거듭제곱을 구하고, 걸린 시간을 나노 세컨드로 반환하는 코드이다. 

#include <iostream>
#include <chrono>

/*Divide&Conquer
* 그대로 해결할 수 없는 문제에 대하여 작은 문제로 분할하여 문제를 해결하는 방식
* Sort Algorithm, FFT Algorithm이 대표적인 예이다
* 보통 재귀 호출로 구현된 함수는 오버헤드 발생의 확률이 있다.
* 
*/

unsigned long int howLong(long double (* fptr)(long double, int), long double num, int exp) {
	std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
	fptr(num, exp);
	std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
	std::chrono::nanoseconds nano = end - start;
	return nano.count();
}

//recursion version
long double pow_v1(long double num, int exp) {
	if (exp == 0) {
		return 1;
	}
	else if (exp == 1) {
		return num;
	}
	if (exp % 2 == 0) {
		long double ans = pow_v1(num, exp / 2);
		return ans*ans;
	}
	else {
		long double ans = pow_v1(num, exp / 2);
		return ans*ans*num;
	}
}

//just recursion
long double pow_v2(long double num, int exp) {
	if (exp == 1) {
		return num;
	}
	if (exp == 0) {
		return 1;
	}
	return pow_v2(num, exp - 1) * num;
}
//simple repeatation
long double pow_v3(long double num, int exp) {
	if (exp == 0) {
		return 1;
	}
	else {
		long double result = 1;
		for (int i = 0; i < exp; i++)
			result *= num;
		return result;
	}
}
//dynamic programming
long double DP[292311] = { 0, };
long double pow_v4(long double num, int exp) {
	if (exp == 1) {
		return num;
	}
	else if (exp == 0) {
		return 1;
	}
	else if (DP[exp] != 0) {
		return DP[exp];
	}
	else {
		DP[exp] = pow_v4(num, exp-1) * num;
		return DP[exp];
	}
}

int main() {
	//D&C
	std::cout <<"1.0000001, 292 : " << pow_v1(1.0000001, 292) << " Time : " << howLong(pow_v1, 1.0000001, 292)<< "ns" << std::endl;
	//Recursion
	std::cout <<"1.0000001, 292 : " << pow_v2(1.0000001, 292) << " Time : " << howLong(pow_v2, 1.0000001, 292) << "ns" << std::endl;
	//Just Repeatation
	std::cout <<"1.0000001, 292 : " << pow_v3(1.0000001, 292) << " Time : " << howLong(pow_v3, 1.0000001, 292) << "ns" << std::endl;
	//Dynamic Programming
	std::cout << "1.0000001, 292 : " << pow_v4(1.0000001, 292) << " Time : " << howLong(pow_v4, 1.0000001, 292) << "ns" << std::endl;
	return 0;
}

 결과는 다음과 같이 나온다. 결과를 보면서 분할 정복의 중요성도 느꼈다. 동시에 재귀함수를 사용하면서 오버헤드가 터져서 오류가 뜨는 것을 보면서 재귀 함수가 유용한 도구이면서 동시에 남발해서는 안된다는 생각이 크게 들었다. (결과를 보면 어설프게 쓴 재귀 함수는 프로그램의 질을 떨어뜨린다는 것을 알 수 있다!!)

위에서 부터 분할정복, 재귀, 단순반복, 다이나믹