분할정복을 이용한 거듭제곱

어떤 수의 제곱은 해당 수를 두 번을 곱함으로써 구할 수 있다. 이는 제곱식의 지수가 커지더라도 같으며 커지면 지수가 커지면 커질 수록 시간이 오래 걸린다. 

 

예를 들어, 11의 12 제곱은 다음과 같이 구할 수 있다. 

int result = 1;
for (int i = 0; i < 12; i++) {
	result *= 11;
}

System.out.println(result);

 

위와 같은 식에서 지수가 한없이 커진다면 해당하는 시간 만큼 반복문이 돌아야 하기 때문에 시간 복잡도는 O(N)이 걸린다. 위의 식을 더 빠르게 계산할 수는 없을까? 

 

분할정복을 이용한 거듭제곱은 위에 대한 해결 방식이다. 예를 들어 11의 12 제곱은 11의 6제곱과 11의 6제곱의 곱을 통하여 구할 수 있는데 이처럼 분할하여 계산을 하고 제곱의 값을 구하면 시간 복잡도는 매 계산 마다 반으로 줄게 된다. 따라서 O(logN)이 된다.

 

그러면 지수가 홀수인 경우에는 어떻게 구하면 좋을까? 지수가 홀수인 경우 밑을 한번 더 곱해주면 된다. 따라서 11의 13제곱은 13을 반으로 내누고 내림한 수인 6제곱  X 6제곱 X 밑 수를 통해서 구할 수 있다. 이러한 식을 일반 식으로 바꿔보면

밑이 C고 지수가 n인 수에서 

 

위와 같이 나눌 수 있다. 이를 코드로 옮기면 다음과 같이 작성하면 된다. 

private static long dpow(long C, long n) {
	if (n == 1) {
    	return C;
    }
	
    long next = dpow(C, n / 2);
    if (n % 2 == 0) {
    	return next * next;
    } else {
    	return next * next * C;
    }
}

 

위에 대한 예시로 다음 문제에서 O(N)에 해당하는 제곱을 구하는 방법을 사용할 경우 시간초과가 나기 때문에 분할정복을  통하여 풀이 방법을 고안해 낼 수 있다.

https://www.acmicpc.net/problem/1629

1629번: 곱셈