문제 개요
이 문제에서는 두 정수 x와 y가 주어집니다. 우리의 과제는 C++ 표준 라이브러리의 pow(x, y)와 동일한 결과를 반환하는 함수를 반복(iterative) 방식으로 직접 작성하고, 시간 복잡도를 O(log y)로 만드는 것입니다.
예시를 통해 문제를 먼저 살펴보겠습니다.
입력
x = 7, y = 3
출력
343
7의 3제곱은 7 × 7 × 7 = 343으로 계산됩니다.
알고리즘 핵심 아이디어
이 문제의 핵심은 거듭제곱 빠른 계산법(Exponentiation by Squaring)입니다. 반복문을 돌면서 다음 두 가지 규칙을 적용합니다.
- y가 홀수일 때마다 결과값(result)에 현재 x를 곱합니다.
- 매 반복마다 x를 제곱(x²)으로 갱신하고, y는 절반으로 줄입니다.
단순히 x를 y번 곱하는 O(y) 방식과 달리, 지수를 절반씩 줄여 나가기 때문에 훨씬 효율적으로 계산할 수 있습니다.
구현 예제
#include <iostream>
using namespace std;
void calcPower(int x, unsigned int y) {
int result = 1;
while (y > 0) {
if (y & 1)
result *= x;
y = y >> 1;
x = x * x;
}
cout << result;
}
int main() {
int x = 7;
unsigned int y = 3;
cout << x << " raised to " << y << " is ";
calcPower(x, y);
return 0;
}
출력 결과
7 raised to 3 is 343
동작 원리 상세 분석
x = 7, y = 3일 때 코드의 실행 흐름을 단계별로 살펴보겠습니다.
- 1회전: y = 3은 홀수이므로 result = 1 × 7 = 7. 이후 y를 오른쪽 시프트하여 1로 만들고, x는 7² = 49가 됩니다.
- 2회전: y = 1 역시 홀수이므로 result = 7 × 49 = 343. y는 0이 되고, x는 49² = 2401이 됩니다.
- 3회전: y = 0이므로 반복문이 종료되고, 최종 결과 343이 출력됩니다.
코드의 핵심 요소
y & 1: 비트 AND 연산으로 y의 홀짝 여부를 판별합니다. 마지막 비트가 1이면 홀수입니다.y >> 1: 오른쪽 비트 시프트로 y를 2로 나눈 몫을 구합니다.x = x * x: 매 반복마다 밑(base)을 제곱하여, 지수를 절반으로 나누는 효과를 얻습니다.
복잡도 분석
각 반복마다 지수 y가 절반씩 감소하므로 시간 복잡도는 O(log y)입니다. 추가적인 배열이나 재귀 호출 스택을 사용하지 않으므로 공간 복잡도는 O(1)로 상수 수준을 유지합니다. 이러한 특성 덕분에 큰 지수에 대해서도 빠르게 거듭제곱을 계산할 수 있으며, 암호학 알고리즘이나 모듈러 거듭제곱 계산 등 다양한 분야에서 널리 활용되는 기법입니다.