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

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

- C**n연산은 x를 n번 곱하므로 O(N)이지만, 이 방법을 사용하면 O(logN)에 거듭제곱 값을 구할 수 있다.

- 아래 코드에서 fpow함수가 그 방법이다.

- n이 1이면 그냥 C의 1제곱이므로 return C를 해준다.

- n이 2이상일 때, C의 n제곱은 다음과 같다.

- n이 짝수이면 윗줄의 식을 만족하고, n이 홀수이면 아래줄의 식을 만족한다.

 

코드로 짜면 다음과 같다.

1. 재귀사용

def fpow(C, n):
	if n == 1:
		return C
	else:
		x = fpow(C, n//2)
		if n % 2 == 0:
			return x * x
		else:
			return x * x * C

2. 반복문 사용

 - n & 1은 n이 짝수이면 0이므로 False이고, n이 홀수이면 1이어서 True이다.) 

 - n >> 1은 비트연산에서 오른쪽으로 비트를 하나씩 미는 것이다. 즉, n //= 2와 같다)

 - 반복문이 약간 빠르다.

def fpow(C, n):
	res = 1
	while n:
		if n & 1:
			res *= C
		C *= C;
		n >> 1
        
	return res

 

대표적인 문제들로는

www.acmicpc.net/problem/18291

www.acmicpc.net/problem/1629

등등이 있다.