[알고리즘] 고속 거듭제곱 연산 - travelbeeee

안녕하세요, 트레블비입니다.

오늘은 빠르게 어떤 수의 N 제곱 구하기에 대해서 포스팅하겠습니다.

---

[O(N) 으로 구하기]

 

예를 들어, 2의 100 제곱을 구한다고 해봅시다. ( Int 형 범위는 고려하지 않겠습니다. )

2를 계속 100번 곱하면 간단하게 답을 얻을 수 있겠죠? 

int answer = 1;
for(int i = 0; i < 100; i++)
	answer = answer * 2;
//주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다. 

 

그렇다면, 2의 100,000,000,000(1000억) 제곱을 구한다고 한다면 2를 계속 곱해가는 방법으로 빠르게 풀 수 있을까요??

int answer 1;
for(int i = 0; i < 100000000000; i++)
	answer = answer * 2;
//주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다.

당연히 1000억 번의 연산이 필요하므로 시간이 엄청 오래 걸립니다.

어떤 수 A의 N제곱을 구해야 되는데 N이 굉장히 크다면,  위의 방법은 시간 복잡도가 O(N)으로 사용할 수 없습니다.

 

[O(logN) 으로 구하기]

 

똑같이 2의 100 제곱을 구한다고 해봅시다. ( Int 형 범위는 고려하지 않겠습니다. )

100은 64 + 32 + 4 로 표현할 수 있습니다. 즉, 100 = 1100100(2) 입니다.

당연히, 모든 수는 2진수로 표현이 가능합니다!

이 사실을 이용해 훨씬 더 빠르게 2의 100 제곱을 구해보겠습니다.

int answer = 1, A = 2, N = 100;
while(N){
  if (N & 1)
  	answer = answer * A;
  N = N / 2;
  A = A * A;
}
//주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다.

 

A = 2, N은 100 = 1100100(2) 이고 마찬가지로 2^100인 A^N을 구하는 코드입니다.

 

먼저, 코드를 살펴보겠습니다.

N = 100 = 1100100(2) 이고, A는 2, Answer = 1로 시작합니다.

N & 1 은 N의 마지막 비트와 1을 And연산을 취하는 것으로, N & 1 은 False입니다.

따라서 answer는 그대로 1이고, N = N / 2 이므로 N = 50 = 110010(2)로 마지막 비트가 사라지고,

A = A * A ; 로 2^2인 4가 됩니다.

 

이 과정을 반복하면 아래 표와 같이 작동합니다.

단계	Answer = 1	A = 2	N = 1100100(2)
1	1	2^2	110010(2)
2	1	2^4	11001(2)
3	2^4	2^8	1100(2)
4	2^4	2^16	110(2)
5	2^4	2^32	11(2)
6	2^4 * 2^32 = 2^36	2^64	1(2)
7	2^4 * 2^32 * 2^64 = 2^100	2^128	0(2)

#주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다.

 

100번의 연산이 아니라, 각 단계마다 3번의 연산으로 무려 7단계 만에 답을 구할 수 있습니다.

N이 커지면 커질수록 처음의 알고리즘보다 훨씬 더 빠르게 작동하겠죠?

잘 익혀두시면 정말 유용하게 사용하는 알고리즘입니다!

 

함수로 표현하면 다음과 같습니다.

long long math_pow(long long x, long long y)
{
	long long tmp = 1;
	while (y)
	{
		if (y & 1)
			tmp = tmp * x;
		y = y / 2;
		x = x * x;
	}
	return tmp;
}

당연히, A^N이 Int 나 long long 형 범위를 넘어가는 문제들은 A^N 을 어떤 수로 나눈 나머지를 구해달라 합니다!

아래와 같이 함수로 표현할 수 있습니다.

long long math_pow(long long x, long long y)
{
	long long tmp = 1;
	while (y)
	{
		if (y & 1)
			tmp = tmp * x % m;
		y = y / 2;
		x = x * x % m;
	}
	return tmp;
}

---

오늘의 포스팅은 여기서 마치겠습니다.

[추천문제]
https://www.acmicpc.net/problem/1629