예를 들어, 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;
}
