이 문제에서는 두 개의 정수 x와 n이 주어지며, 우리의 목표는 x의 n제곱, 즉 pow(x, n) 값을 계산하는 프로그램을 작성하는 것입니다.
먼저 예시를 통해 문제를 이해해 보겠습니다.
입력
x = 5 , n = 3
출력
125
즉, 5를 3번 곱한 값인 125가 결과가 됩니다.
pow(x, n) 계산 프로그램
아래는 재귀적 분할 정복(Divide and Conquer) 기법을 활용하여 거듭제곱을 효율적으로 계산하는 C++ 코드입니다.
예제 코드
#include <iostream>
using namespace std;
float myPow(float x, int y) {
if(y == 0)
return 1;
float temp = myPow(x, y / 2);
if (y % 2 == 0)
return temp*temp;
else {
if(y > 0)
return x*temp*temp;
else
return (temp*temp)/x;
}
}
int main() {
float x = 5;
int n = 7;
cout<<x<<" raised to the power "<<n<<" is "<<myPow(x, n);
return 0;
}출력 결과
5 raised to the power 7 is 78125
코드 동작 원리
이 프로그램은 단순히 x를 n번 곱하는 대신, 지수를 절반으로 나누어 계산하는 빠른 거듭제곱(Fast Exponentiation) 기법을 사용합니다.
동작 과정은 다음과 같습니다.
- 지수 y가 0이면 항상 1을 반환합니다.
- x^(y/2)를 먼저 재귀적으로 계산한 뒤, 그 결과를 제곱합니다.
- y가 짝수라면 temp × temp가 곧 x^y가 됩니다.
- y가 홀수라면 x를 한 번 더 곱해주어 x^y를 완성합니다.
- y가 음수인 경우에도 (temp × temp) / x 형태로 처리하여 음수 지수까지 올바르게 계산합니다.
시간 복잡도
단순 반복으로 거듭제곱을 계산하면 O(n)의 시간이 걸리지만, 이 방식은 매 단계마다 지수를 절반으로 줄이기 때문에 시간 복잡도가 O(log n)으로 크게 향상됩니다. 따라서 n이 매우 큰 경우에도 빠른 속도로 결과를 얻을 수 있습니다.