C++로 숫자의 다섯 제곱근(5제곱근) 내림값 구하기

이 문제에서는 숫자 N이 주어지며, 우리가 해야 할 일은 N의 다섯 제곱근(5제곱근)에 대한 내림값(floor value)을 구하는 것입니다.

어떤 수의 다섯 제곱근이란, 그 수를 스스로에게 5번 곱했을 때 원래의 수가 되는 값을 의미합니다.

즉, N^1/5 = a 라면, a × a × a × a × a = N 이 성립합니다.

예시를 통해 문제 이해하기

입력: N = 325

출력: 3

설명:

325의 다섯 제곱근은 약 3.179이며, 이 값의 내림값은 3입니다.

해결 접근 방법

방법 1: 단순 선형 탐색

가장 간단한 해결 방법은 1부터 n까지 차례대로 탐색하면서, 자기 자신을 다섯 번 곱했을 때 n이 되는 수를 찾는 것입니다.

하지만 주어진 수가 항상 완전한 다섯 제곱수인 것은 아니므로 정확한 값을 구할 수 없습니다. 따라서 다섯 제곱한 값이 처음으로 n보다 커지는 지점을 찾고, 그 값에서 1을 뺀 결과를 반환하여 내림값을 얻는 방식을 사용합니다.

구현 예제 코드

#include<iostream>
using namespace std;

int calcFifthRoot(int n) {
   
   if (n == 0 || n == 1)
      return n;

   int a = 0;
   for(a = 1; a*a*a*a*a < n ; a++){
     
   }
   return (a - 1);
}

int main() {
   
   int n = 325;
   cout<<"The Floor of fifth root of "<<n<<" is "<<calcFifthRoot(n);
   return 0;
}

출력 결과

The Floor of fifth root of 325 is 3

방법 2: 이진 탐색(Binary Search) 활용

위의 알고리즘도 충분히 동작하지만, 시간 복잡도 측면에서 더 효율적인 방법이 있습니다. 바로 탐색 과정을 개선하여 이진 탐색(binary search) 알고리즘으로 다섯 제곱근을 찾는 것입니다.

탐색 범위를 절반씩 줄여나가기 때문에 선형 탐색(O(n))보다 훨씬 빠른 O(log n)의 시간 복잡도로 답을 구할 수 있습니다.

구현 예제 코드

#include<iostream>
using namespace std;

int calcFifthRoot(int n)
{
   if (n == 0 || n == 1)
   return n;

   int start = 1, end = n, root = 0;
   while (start <= end)
   {
      int a = (start + end) / 2;
      long int apowfive = a*a*a*a*a;

      if (apowfive == n)
         return a;
      if (apowfive < n) {
         
         start = a + 1;
         root = a;
      }
      else
         end = a - 1;
   }
   return root;
}

int main() {
   
   int n = 250;
   cout<<"The floor of fifth root of "<<n<<" is "<<calcFifthRoot(n);
   return 0;
}

출력 결과

The floor of fifth root of 250 is 3

마무리

정리하자면, 숫자 N의 다섯 제곱근 내림값을 구하는 문제는 두 가지 방식으로 해결할 수 있습니다. 첫 번째는 1부터 n까지 순차적으로 확인하는 선형 탐색 방식이고, 두 번째는 탐색 범위를 반복적으로 절반으로 줄여가는 이진 탐색 방식입니다. 입력값이 클수록 이진 탐색 방식이 압도적으로 효율적이므로, 실제 코딩 테스트나 알고리즘 문제에서는 이진 탐색 기반 풀이를 사용하는 것이 좋습니다.