C++에서 숫자의 N제곱근 구하는 방법

문제 개요

N제곱근의 차수 N과 그 계산 결과가 주어졌을 때, number^N = result를 만족하는 숫자를 찾는 것이 목표입니다.

예시를 통해 문제를 이해해 보겠습니다.

예제 1

입력

result = 25
N = 2

출력

5

5² = 25이므로, 위 예제의 정답은 5입니다.

예제 2

입력

result = 64
N = 3

출력

4

4³ = 64이므로, 위 예제의 정답은 4입니다.

알고리즘

가장 직관적인 해결 방법은 완전 탐색(Brute Force)입니다. 1부터 시작하여 숫자를 하나씩 늘려가며 해당 숫자의 N제곱이 result와 일치하는지 확인합니다.

1. 탐색 변수 i를 1로 초기화합니다.
2. i의 N제곱(i^N)이 result와 같은지 검사합니다.
3. 같다면 i가 곧 원하는 N제곱근이므로 i를 반환합니다.
4. 같지 않다면 i를 1 증가시키고 2번 과정부터 반복합니다.

이 방법의 시간 복잡도는 정답 값에 비례하며, result가 어떤 정수의 완전한 N제곱수일 때만 동작한다는 점에 유의해야 합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>

using namespace std;

int getNthRoot(int result, int n) {
    int i = 1;
    while (true) {
        if (pow(i, n) == result) {
            return i;
        }
        i += 1;
    }
}

int main() {
    int result = 64, N = 6;
    cout << getNthRoot(result, N) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

2

2⁶ = 64이므로, result가 64이고 N이 6일 때 정답은 2가 됩니다.

참고 사항

위 구현은 result가 정확히 어떤 정수의 N제곱인 경우에만 유효합니다. 만약 완전한 N제곱수가 아니라면 무한 루프에 빠질 수 있습니다. 실무에서는 round(pow(result, 1.0 / n))처럼 부동소수점 연산을 활용한 뒤 검증하는 방식으로 보완할 수 있습니다.