Math.sqrt() 없이 제곱근 구하기: 자바스크립트 이진 탐색 알고리즘

자바스크립트에서 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){
        // n이 완전제곱수인 경우
        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));

코드 동작 원리

이 코드의 핵심 로직은 다음과 같이 두 단계로 나눌 수 있습니다.

1단계: 제곱근이 존재하는 범위 찾기

i = 1부터 시작하여 반복문을 돌립니다. 만약 i * i === num이라면 num은 완전제곱수이므로 그대로 i를 반환하면 됩니다. 그렇지 않다면 i * i가 처음으로 num보다 커지는 지점을 찾습니다.

이 시점에서 우리는 num의 제곱근이 반드시 i - 1과 i 사이에 존재한다는 것을 알 수 있습니다.

2단계: 이진 탐색으로 정밀한 값 찾기

범위를 좁혔다면, 이제 이진 탐색 알고리즘을 사용해 정확한 제곱근 값을 찾아냅니다.

• 구간의 중간값 mid를 구하고, mid * mid를 계산합니다.
• 그 결과가 n과 같거나 오차가 0.00001 미만이면 mid를 반환합니다.
• mid * mid가 n보다 작으면 탐색 범위를 오른쪽 절반으로 좁히고,
• n보다 크면 왼쪽 절반으로 좁혀 재귀적으로 탐색을 반복합니다.

오차 허용 범위(0.00001)를 두는 이유는 대부분의 숫자가 완전제곱수가 아니어서 부동소수점 연산으로 정확히 일치하는 값을 찾기 어렵기 때문입니다.

실행 결과

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

5.744562149047852

실제로 √33 ≈ 5.744562...이므로, Math.sqrt()를 사용하지 않고도 매우 정확한 제곱근 값을 얻은 것을 확인할 수 있습니다.

마무리

이 방식의 시간 복잡도는 이진 탐색 덕분에 O(log n) 수준으로 효율적입니다. 뉴턴-랩슨법(Newton-Raphson method) 등 다른 수치 해석 기법도 있지만, 이진 탐색은 직관적이고 구현이 간단하여 면접에서 설명하기에도 좋은 접근 방식입니다.