[LeetCode] 69. Sqrt(x) (C++)

Problem Overview

https://leetcode.com/problems/sqrtx/description/?envType=problem-list-v2&envId=math

Sqrt(x) - LeetCode

 

69. Sqrt(x)

이 문제는, 음의 정수가 아닌 integer x가 input으로 들어왔을 때, 제곱근을 구하는 문제이다. 실수 제곱근이 아닌 가까운 정수로 내림하여 정수로 반환하면 되는 문제이다. 조건은, pow 등 내장된 함수를 사용하면 안된다.

Approach

일단 먼저 결과를 반환할 때, 가까운 정수로 내림하여 반환한다는 것은 int 특성상 어차피 내림을 해서 반환해주니, 신경쓰지 않아도 된다.

문제는 내장된 제곱근 함수를 사용하지 않고 문제를 푸는 것이다. 일단 가장 먼저 떠오른 방법은 Binary Search로 근사값을 구하는 방식이 생각났다.

Binary Search를 생각한 이유는 다음과 같다.

먼저 이 문제에서 우리가 찾으려는 값 ans라고 하면, ans 는 다음 조건을 만족해야한다.
$$
ans^2 \le x < (ans + 1)^2
$$
이때 ans가 될 수 있는 후보 숫자의 범위는 0부터 x까지이다. 이 숫자들은 오름차순으로 정렬되어 있다고 볼 수 있다. 그렇다면 어떤 수 k를 선택했을 때,

• $k^2$이 $x$보다 크다면? $\rightarrow$ $k$보다 큰 모든 수는 답이 될 수 없다.(범위를 왼쪽으로 좁힌다.)
• $k^2$이 $x$보다 작거나 같다면? $\rightarrow$ $k$는 답의 후보가 될 수 있고, 더 큰 값 중에 답이 있는지 확인해야 한다.(범위를 오른쪽으로 좁힌다.)

이런 방식으로 정렬된 범위 내에서 특정 조건을 만족하는 값을 찾는 이진 탐색은 $O(log \, x)$의 시간 복잡도를 갖는다. 매우 효율적이라고 할 수 있다.

Pseudo-code는 다음과 같다.

function mySqrt(x):
    if x < 2: return x  // 0과 1은 자기 자신이 제곱근

    low = 2, high = x / 2  // x가 4 이상일 때 제곱근은 항상 x/2보다 작거나 같음
    ans = 1

    while low <= high:
        mid = low + (high - low) / 2 

        if mid * mid == x:
            return mid
        else if mid * mid < x:
            ans = mid
            low = mid + 1
        else:
            high = mid - 1

    return ans

여기서 주의할 점은 mid의 type을 long long으로 해야한다는 점이다. 조건문에서 mid * mid 연산을 해야하는데 int이면 Runtime Error가 발생할 수 있기 때문이다.

이 문제를 풀다 보니, 수치해석에서 배웠던 Newton's Method가 생각나서 더 간단하게 코드를 작성할 수 있겠다고 생각했다. 또한 뉴턴 방법은 이차 수렴하므로 이진 탐색보다 훨씬 빠르게 수렴하게 된다는 장점이 있다.(물론 장점만 있는 것은 아니다.)

원리는 간단하게 말하면, 함수의 접선을 이용하여 근사해를 구하는 방식인데, $f(x) = k^2 - x = 0$이 되는 $k$를 찾는 것을 목표로한다고 생각하면 된다.

정수 제곱근을 구하기 위한 뉴턴 방법의 점화식은 다음과 같이 세울 수 있다.
$$k_{n+1} = \lfloor \frac{1}{2} (k_n + \frac{x}{k_n}) \rfloor$$
알고리즘 흐름은 다음과 같다.

• 1. 초기값 설정 : $k$의 초기값을 $x$로 설정한다.(x/2도 써도 되긴 하다.)
• 2. 반복 : $k_{n+1} < k_n$인 동안 계속 업데이트한다.
• 3. 종료 : 더 이상 값이 작아지지 않으면 (즉, $k^2 \le x$인 지점에 도달하면) 그 값이 정답인 제곱근이 된다.

마찬가지로 구현할 때 Integer Overflow 방지를 위해서 long long 타입을 사용해줘야 한다. Pseudo Code는 다음과 같다.

// Newton's Method Pseudo-code
long long r = x;
while (r * r > x) {
    r = (r + x / r) / 2;
}
return r;

Code

Binary Search

class Solution {
public:
    int mySqrt(int x) {
        if( x < 2) return x;

        int low = 2;
        int high = x/2;
        int ans = 1;

        while(low <= high){
            long long mid = low + (high-low)/2;

            long long mm = mid * mid;

            if(mm == x) return mid;
            else if(mm < x) {
                ans = mid;
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return ans;
    }
};

Newton's Method

class Solution {
public:
    int mySqrt(int x) {
        if(x <= 1) return x;

        long long r = x;
        while(r*r > x){
            r = (r + x/r) /2;
        }
        return r;
    }
};

Review

간단한 이분탐색 또는 뉴턴의 기법 같은 수치해석 알고리즘을 이용하면 풀리는 문제였다. 주의할 점은 Integer Overflow 방지를 위해 Type을 잘 설정해주는 것과, 위에서 언급은 안했지만, 0으로 나누기 방지를 위해서 초반에 예외 처리를 해주는 것도 중요하다고 생각한다.