숫자의 거듭제곱은 x^y 형태로 표현할 수 있으며, 여기서 x는 밑(base)이 되는 숫자이고 y는 지수(exponent)입니다.
예를 들어 다음과 같습니다.
x = 2, y = 10일 때
x^y = 2^10 = 1024
거듭제곱은 반복문을 사용하는 비재귀 방식과 재귀 함수를 사용하는 방식, 두 가지 방법으로 계산할 수 있습니다. 각각의 구현 방법을 아래에서 자세히 살펴보겠습니다.
반복문을 이용한 거듭제곱 계산 (비재귀 방식)
반복문을 사용해 숫자의 거듭제곱을 구하는 프로그램은 다음과 같습니다.
예제 코드
#include<iostream>
using namespace std;
int power(int x, int y) {
int i, power = 1;
if(y == 0)
return 1;
for(i = 1; i <= y; i++)
power = power * x;
return power;
}
int main() {
int x = 3;
int y = 4;
cout<<"x = "<<x<<endl;
cout<<"y = "<<y<<endl;
cout<<"x^y = "<<power(x,y);
return 0;
}
실행 결과
x = 3
y = 4
x^y = 81
코드 설명
위 프로그램에서 power() 함수는 숫자의 거듭제곱을 계산하는 비재귀(non-recursive) 함수입니다. 함수 내부에는 1부터 y까지 반복하는 for 루프가 있으며, 루프가 한 번 실행될 때마다 x가 power 변수에 곱해집니다.
결국 x가 자기 자신과 y번 곱해지면서 그 결과가 power에 저장되고, 이 값이 곧 x^y가 됩니다. 마지막으로 power 값을 main() 함수로 반환합니다.
핵심 로직은 다음 코드 조각과 같습니다.
int power(int x, int y) {
int i, power = 1;
if(y == 0)
return 1;
for(i = 1; i <= y; i++)
power = power * x;
return power;
}main() 함수에서는 x, y, 그리고 x^y의 값을 화면에 출력합니다.
cout<<"x = "<<x<<endl;
cout<<"y = "<<y<<endl;
cout<<"x^y = "<<power(x,y);
재귀 함수를 이용한 거듭제곱 계산
재귀(recursion)를 활용하면 지수를 절반씩 줄여가며 더 효율적으로 거듭제곱을 계산할 수 있습니다. 프로그램은 다음과 같습니다.
예제 코드
#include<iostream>
using namespace std;
int power(int x, int y) {
if (y == 0)
return 1;
else if (y % 2 == 0)
return power(x, y/2) * power(x, y/2);
else
return x * power(x, y/2) * power(x, y/2);
}
int main() {
int x = 3;
int y = 4;
cout<<"x = "<<x<<endl;
cout<<"y = "<<y<<endl;
cout<<"x^y = "<<power(x,y);
return 0;
}
실행 결과
x = 3
y = 4
x^y = 81
코드 설명
위 프로그램의 power() 함수는 재귀적으로 동작하며, 작동 원리는 다음과 같습니다.
- y가 0이면 1을 반환합니다. (모든 수의 0제곱은 1)
- y가 짝수이면 x와 y/2를 인자로 자기 자신을 호출한 결과를 두 번 곱해 반환합니다.
- y가 홀수이면 위 결과에 x를 한 번 더 곱해 반환합니다.
핵심 로직은 다음 코드 조각으로 확인할 수 있습니다.
int power(int x, int y) {
if (y == 0)
return 1;
else if (y % 2 == 0)
return power(x, y/2) * power(x, y/2);
else
return x * power(x, y/2) * power(x, y/2);
}main() 함수에서는 x, y, x^y 값을 출력합니다.
cout<<"x = "<<x<<endl;
cout<<"y = "<<y<<endl;
cout<<"x^y = "<<power(x,y);
마무리: 어떤 방법을 선택해야 할까?
두 방식 모두 동일한 결과를 출력하지만 성능에는 차이가 있습니다. 재귀 방식은 지수를 절반씩 나누어 계산하므로 시간 복잡도가 O(log n)으로 더 효율적입니다. 반면 반복문 방식은 O(n)의 시간이 걸리지만 코드가 직관적이라 이해하고 디버깅하기 쉽습니다. 입력 크기와 상황에 맞게 적절한 방법을 선택하는 것이 좋습니다.