01. 제곱 알고리즘

2023. 3. 8. 23:20

이번에 테스트를 한번 해봤는데 내장 함수들에 너무 의존적이라는 것을 알게 되어서 알고리즘 글을 올리게 되었습니다.

\(a^{n} = a * a * a ...\)

먼저 가장 쉬운 제곱 알고리즘의 경우는 아래와 같습니다.

int n = 10;
int num = 3;
int answer = 1;

for (int i = 0; i < n; i++)
{
	answer *= num;
}

cout << answer << endl;
// 59049

위와 같은 알고리즘은 지수 n번만큼 num을 곱해주게 되므로 시간복잡도는 O(n)이 됩니다.

하지만 더욱 효과적인 O(logn) 방법이 있다는걸 이번에 알게 되었습니다.

int n = 10;
int num = 3;
int answer = 1;

while (n)
{
	if (n & 1)
	{
		answer *= num;
	}
	n = n >> 1;
	num *= num;
}
cout << answer << endl;
// 59049

지수 10은 2진수로 1010(2)와 같이 표현되고

1010(2) = 1000(2) + 10(2) = 2^3 + 2^1 로도 표현할 수 있습니다.

비트연산자로 1010(2)를 1과 and 연산을 해주어 0일 경우,

비트를 오른쪽으로 옮겨주면서 숫자 num을 제곱해줍니다.

1일 경우에는 answer에 num을 곱해주고 숫자 num을 제곱해줍니다.

그렇다면 총 10번을 곱해줘야 할 계산을 4번만에 해결할 수 있게 됩니다.

IT 공부방