두 개의 입력값 x와 n이 주어집니다. 여기서 x는 -100.0부터 100.0 사이의 실수이고, n은 32비트 부호 있는 정수입니다. 이때 라이브러리 함수를 사용하지 않고 x의 n제곱(xⁿ)을 직접 계산해야 합니다.
예를 들어 x = 12.1, n = -2가 입력으로 주어지면 결과는 0.00683이 됩니다.
문제 해결 접근 방법
이 문제는 빠른 거듭제곱(Exponentiation by Squaring) 기법을 활용하면 효율적으로 해결할 수 있습니다. 지수를 이진수로 보고 비트 연산을 활용하면 단순 반복 곱셈보다 훨씬 적은 연산 횟수로 답을 구할 수 있으며, 시간 복잡도는 O(log n)입니다.
구체적인 알고리즘은 다음과 같습니다.
- power 변수에 n의 절댓값(|n|)을 저장하고, 결과값 res는 1.0으로 초기화합니다.
- power가 0이 아닌 동안 다음 과정을 반복합니다.
- power의 마지막 비트가 1이면 res에 현재 x를 곱합니다.
- x를 자기 자신으로 곱해 제곱합니다 (x = x * x).
- power를 오른쪽으로 한 비트 시프트합니다 (power >>= 1).
- n이 음수였다면 1 / res를 반환합니다.
- 그렇지 않다면 res를 그대로 반환합니다.
핵심 아이디어는 지수를 이진수로 분해하는 것입니다. 예를 들어 13 = 1101₂이므로, x¹³ = x⁸ × x⁴ × x¹처럼 필요한 거듭제곱 값만 곱하면 됩니다. 매 반복마다 x를 제곱해 나가면서, 해당 비트가 1일 때만 결과에 곱해주는 방식입니다. 또한 n이 음수인 경우에는 양수 지수로 계산한 뒤 역수를 취하면 됩니다.
파이썬 구현 예제
아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
class Solution(object):
def myPow(self, x, n):
power = abs(n)
res = 1.0
while power:
if power & 1:
res *= x
x *= x
power >>= 1
if n < 0:
return 1 / res
return res
ob1 = Solution()
print(ob1.myPow(45, -2))
print(ob1.myPow(21, 3))입력
45 -2 21 3
출력
0.0004938271604938272 9261.0
첫 번째 호출에서는 45의 -2제곱, 즉 1/(45²) = 0.0004938271604938272가 출력되고, 두 번째 호출에서는 21³ = 9261.0이 출력됩니다. 이처럼 비트 연산 기반의 빠른 거듭제곱 알고리즘을 사용하면 큰 지수에 대해서도 매우 빠르게 결과를 얻을 수 있습니다.