문제 개요
이번 글에서는 Math.sqrt() 메서드를 사용하지 않고, 음수가 아닌 정수의 제곱근을 계산해 반환하는 자바스크립트 함수를 작성하는 방법을 알아보겠습니다.
요구 사항은 다음과 같습니다. 함수는 음수가 아닌 정수를 인자로 받아 제곱근을 계산한 뒤 반환해야 하며, 소수점 이하 값은 버리고(내림하여) 정수만 반환하면 됩니다.
예를 들어 입력값이 15라면 정확한 제곱근(약 3.87)을 반환할 필요가 없습니다. 15보다 작거나 같은 가장 가까운 정수인 3을 반환하면 충분합니다.
접근 방식: 이진 탐색(Binary Search)
이 문제는 이진 탐색 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 0부터 num까지의 범위에서 중간값(mid)을 구하고, 그 값을 제곱한 결과를 목표 값과 비교하며 탐색 범위를 절반씩 줄여 나가는 방식입니다.
- mid² === num인 경우 → mid가 정확한 제곱근이므로 즉시 반환합니다.
- mid² > num인 경우 → 제곱근은 mid보다 작으므로 탐색 상한을 mid − 1로 줄입니다.
- mid² < num인 경우 → 제곱근은 mid보다 크므로 탐색 하한을 mid + 1로 올립니다.
루프가 종료되면 변수 r에는 목표 값의 제곱근을 넘지 않는 가장 큰 정수가 저장되어 있으므로, 이 값을 최종 결과로 반환합니다.
코드 예제
const squareRoot = (num = 1) => {
let l = 0;
let r = num;
while(l <= r) {
const mid = Math.floor((l + r) / 2);
if(mid ** 2 === num){
return mid;
} else if(mid ** 2 > num){
r = mid - 1;
} else {
l = mid + 1;
};
};
return r;
};
console.log(squareRoot(4));
console.log(squareRoot(729));
console.log(squareRoot(15));
console.log(squareRoot(54435));실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
2 27 3 233
결과 해석
- 4 → 2: 2² = 4이므로 정확한 제곱근입니다.
- 729 → 27: 27² = 729이므로 정확한 제곱근입니다.
- 15 → 3: 3² = 9 ≤ 15이고 4² = 16 > 15이므로 내림한 값입니다.
- 54435 → 233: 233² = 54289 ≤ 54435이고 234² = 54756 > 54435이므로 내림한 값입니다.
이진 탐색을 사용하기 때문에 시간 복잡도는 O(log n)으로, 큰 수가 입력되더라도 매우 빠르게 제곱근을 구할 수 있다는 장점이 있습니다.