Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 거듭제곱(Power) 개념 이해하고 구현하기

거듭제곱이란 무엇인가?

수학에서 거듭제곱(power)은 어떤 수를 자기 자신과 여러 번 곱하는 것을 의미하며, 지수(exponent) 또는 멱수(indices)라고도 불립니다.

a의 b제곱(ab)은 a를 b번 곱한 값을 뜻합니다. 예를 들어, 7의 2제곱(72, 즉 7의 제곱)은 7 × 7 = 49가 됩니다.

자주 사용되는 거듭제곱의 성질

  • 어떤 수의 0제곱은 항상 1입니다.
  • 어떤 수의 1제곱은 자기 자신과 같습니다. 한 번 곱하면 값이 변하지 않기 때문입니다.
  • 어떤 수의 음수 제곱은 나눗셈으로 표현됩니다. 예를 들어, a-3 = 1/a3 = (1/a) × (1/a) × (1/a) 입니다.

문제 정의

이제 거듭제곱 개념을 프로그래밍으로 적용해 보겠습니다.

두 개의 수 N과 a가 주어졌을 때, N이 a의 거듭제곱인지 판별하는 것이 목표입니다.

예시

입력 — N = 64, a = 2

출력 — Yes (64 = 26이므로)

해결 접근 방법

가장 간단하고 효과적인 방법은 반복적인 곱셈을 활용하는 것입니다. x를 계속 곱해가며 y에 도달하는지 확인하고, 정확히 일치하면 TRUE를, 초과하면 FALSE를 반환합니다.

C++ 구현 코드

#include <iostream>
using namespace std;
bool isAPowerNumber(int x, long int y) {
    if (x == 1)
        return (y == 1);
    long int power = 1;
    while (power < y)
        power *= x;
    return (power == y);
}
int main() {
    int N = 625 , a = 5;
    if(isAPowerNumber(a, N))
        cout<<N<<" is a power of "<<a;
    else
        cout<<N<<" is not power of "<<a;
    return 0;
}

실행 결과

625 is a power of 5

코드 설명

위 코드의 동작 원리는 다음과 같습니다.

  • x가 1인 경우, y도 1일 때만 참을 반환합니다. (1의 거듭제곱은 항상 1이므로)
  • power 변수를 1로 초기화한 후, y보다 작아지는 동안 x를 계속 곱합니다.
  • 반복이 끝난 후 power가 y와 정확히 일치하면 y는 x의 거듭제곱입니다.

이 알고리즘의 시간 복잡도는 O(logyN)으로 매우 효율적이며, 추가 메모리 없이 문제를 해결할 수 있습니다.