라이브러리 함수 없이 숫자의 제곱근 구하기 - JavaScript

JavaScript에서 숫자를 입력받아 그 제곱근을 계산하는 함수를 작성해야 합니다. 단, Math.sqrt()와 같은 내장 라이브러리 함수는 사용할 수 없습니다.

이 문제는 이진 탐색(Binary Search) 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 먼저 완전 제곱수인지 확인한 후, 제곱근이 존재하는 구간을 좁혀 가며 근사값을 찾는 방식입니다.

예제 코드

다음은 전체 구현 코드입니다 −

const square = (n, i, j) => {
   let mid = (i + j) / 2;
   let mul = mid * mid;
   if ((mul === n) || (Math.abs(mul - n) < 0.00001)){
      return mid;
   }else if (mul < n){
      return square(n, mid, j);
   }else{
      return square(n, i, mid);
   }
}
// n의 제곱근을 찾는 함수
const findSqrt = num => {
   let i = 1;
   const found = false;
   while (!found){
      // num이 완전 제곱수인 경우
      if (i * i === num){
         return i;
      }else if (i * i > num){
         let res = square(num, i - 1, i);
         return res;
      };
      i++;
   }
}
console.log(findSqrt(33));

출력 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다 −

5.744562149047852

코드 동작 원리

이 코드가 어떻게 동작하는지 단계별로 살펴보겠습니다.

1단계: 정수 범위 찾기

i = 1부터 시작해 반복문을 실행합니다. 만약 i × i = num이라면 num은 완전 제곱수이므로 i가 곧 제곱근입니다. 그렇지 않다면 i × i가 처음으로 num보다 커지는 지점을 찾습니다.

2단계: 이진 탐색으로 근사값 계산

이 시점에서 num의 제곱근은 반드시 구간 [i − 1, i] 사이에 존재합니다. 이 구간 안에서 이진 탐색을 수행하며, 중간값(mid)의 제곱이 num과 충분히 가까워질 때까지(오차 0.00001 미만) 탐색 범위를 절반씩 줄여 나갑니다.

이 방식은 선형 탐색보다 훨씬 빠르게 수렴하기 때문에 큰 수에 대해서도 효율적으로 제곱근을 구할 수 있습니다.