[Java] Math.sqrt() 함수

Math.sqrt() 함수는 제곱근을 계산하는 데 사용된다.

성능 최적화와 수학적 계산에 주로 사용이 되는데, 그 사용법을 정리하려고 한다.

 

용도

1. 소수 판별 최적화

여기서 말하는 소수란 분수 소수의 소수가 아니라 약수가 1과 자기 자신뿐인 소수를 말한다.

소수 판별을 할 때 모든 수를 나눠보는 대신, 제곱근까지만 확인하면 시간 복잡도를 줄일 수 있다.

예를 들어, n이 소수인지 확인하기 위해서 1부터 n-1까지 나눠볼 수 있지만,

이렇게 되면 시간 복잡도가 O(n)이 된다.

소수가 아니라면 1과 자신 외에 다른 약수가 있기만 하면 되므로

1부터 제곱근 n까지만 확인하면 된다.

이렇게 시간 복잡도를 O(n)에서 O( √ n)으로 줄여줄 수 있다.

<예시 코드>

// n이 소수인지 아닌지 판별하는 메소드
public boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

 

---

 

2. 완전 제곱수 판별 최적화

완전 제곱수(정사각수, 제곱수)란 1, 4, 9, 16, ...처럼 어떤 자연수의 제곱이 되는 수이다.

어떤 수 n이 완전 제곱수인지 확인할 때 Math.sqrt()를 사용하면 매우 효율적이다.

예를 들어 n이 16일 때 Math.sqrt(n)은 4가 되므로,

다시 4를 제곱해서 16과 비교하여 완전 제곱수인지 쉽게 판별할 수 있다.

이 역시 연산 횟수를 크게 줄이기 위함이다.

<예시 코드>

// 완전 제곱수인지 판별하는 메소드
public boolean isPerfectSquare(int n) {
    int sqrt = (int) Math.sqrt(n);
    return sqrt * sqrt == n;
}

 

---

 

3. 이진 탐색(Binary Search)

이진 탐색을 사용할 때, 특히 특정 조건을 만족하는 수를 찾는 문제에서 제곱근 계산이 유용할 수 있다.

예를 들어, 제곱한 값이 n보다 작은 x 중 가장 큰 수를 구하려면,

이진 탐색 대신 Math.sqrt()를 활용할 수 있다.

이를 통해 직접적인 계산 없이 범위를 좁히면서 답을 빠르게 구할 수 있다.

<예시 코드>

자연수 n이 주어졌을 때, 그 제곱근보다 작거나 같은 수 중 가장 큰 정수를 찾아라.

예) n=10이면, x=3

// 1. 이진 탐색으로 제곱근을 구하는 방법 ====================
public class BinarySearchSqrt {
    public static int binarySearchSqrt(int n) {
        int left = 0;
        int right = n;
        int result = 0;

        // 이진 탐색 시작
        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 제곱근을 초과하지 않는 값 중 최대를 찾음
            if (mid * mid <= n) {
                result = mid; // 현재 값 저장
                left = mid + 1; // 더 큰 값 탐색
            } else {
                right = mid - 1; // 더 작은 값 탐색
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("√" + n + "보다 작은 최대 정수는: " + binarySearchSqrt(n));

        int n2 = 50;
        System.out.println("√" + n2 + "보다 작은 최대 정수는: " + binarySearchSqrt(n2));

        int n3 = 1000000;
        System.out.println("√" + n3 + "보다 작은 최대 정수는: " + binarySearchSqrt(n3));
    }
}

// 2. Math.sqrt()를 사용하는 방법 ====================
public class SqrtExample {
    public static int sqrtWithMathSqrt(int n) {
        return (int) Math.sqrt(n);
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("√" + n + "보다 작은 최대 정수는: " + sqrtWithMathSqrt(n));

        int n2 = 50;
        System.out.println("√" + n2 + "보다 작은 최대 정수는: " + sqrtWithMathSqrt(n2));

        int n3 = 1000000;
        System.out.println("√" + n3 + "보다 작은 최대 정수는: " + sqrtWithMathSqrt(n3));
    }
}

<주의점>

🌟 효율만 보자면 Math.sqrt()를 사용하는 것보다 이진 탐색을 사용하는 것이 더 좋다. 🌟

이진 탐색은 코드가 상대적으로 길지만 시간 복잡도가 O(log n)으로 매우 빠르다.

성능 측면에서는 정수 연산만 사용하므로 빠르고 안정적인 것이다.

Math.sqrt()는 위의 예시 코드에서 봤듯이 더 간결하다.

제곱근을 직접 계산하므로 코드가 짧아지고 가독성이 좋아진다.

하지만 실수 연산을 포함하기 때문에 이진 탐색보다 상대적으로 느려질 수 있다.

성능은 O( √ n)이지만, 실수 연산이 반복될 경우 성능 저하가 발생할 수 있다.

 

---

 

4. 정렬과 기하학적 문제

기하학 문제에서 점과 점 사이의 유클리드 거리를 구하거나,

도형의 면적, 둘레, 대각선 등을 구하는 문제에서 제곱근은 필수적이다.

<예시코드>

// 점(x1, y1)과 점(x2, y2) 사이의 거리를 구하는 메소드
public double euclideanDistance(double x1, double y1, double x2, double y2) {
    return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
}

 

---

 

5. 이차 방적식 풀이 최적화

이차 방정식 역시 제곱근이 필수적이다.

큰 숫자나 복잡한 식을 풀 때 Math.sqrt()를 사용하면 빠르고 정확하게 답을 구할 수 있다.

<예시 코드>

// 이차방정식의 해를 구하는 메소드
public double[] solveQuadratic(double a, double b, double c) {
    double discriminant = Math.sqrt(b * b - 4 * a * c);
    return new double[] {
        (-b + discriminant) / (2 * a),
        (-b - discriminant) / (2 * a)
    };
}

 

 

---

 

6. 반복문 내 연산 최적화

수학 문제에서 반복문을 사용하는 경우, 제곱근 계산을 여러 번 할 때

미리 제곱근을 계산해두면 성능을 개선할 수 있다.

예를 들어, 배열 내 숫자들의 제곱근을 구하는 작업에서

미리 제곱근을 저장해 반복문 내에서 재사용할 수 있다.

<예시 코드>

// 배열 내 숫자들의 제곱근을 구하는 메소드
public double[] precomputeSquareRoots(int[] numbers) {
    double[] squareRoots = new double[numbers.length];
    for (int i = 0; i < numbers.length; i++) {
        squareRoots[i] = Math.sqrt(numbers[i]);
    }
    return squareRoots;
}

 

 

---

 

결론

Math.sqrt() 함수는 불필요한 반복 연산을 줄이고 효율적인 계산이 가능하게 한다.

특히, 소수 판별, 완전 제곱수 판별, 기하학적 거리 계산, 이차 방정식 등에서 사용되는 경우,

문제 해결에 필요한 시간 복잡도를 줄여 최적화할 수 있다.

(🌟 이진 탐색 대신 사용할 경우, 연산은 줄일 수 있지만 시간 복잡도는 오히려 늘어난다.)