[leetcode 69] Sqrt(x)

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

 

Example 1:

Input: x = 4 Output: 2

Example 2:

Input: x = 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

 

Constraints:

• 0 <= x <= 2^31 - 1

난이도 : 쉬움

 

문제 풀이: 모야 쉽다며..

brute force해도 풀리긴한다. x가 int_max까지만 이기 때문이다.

 

class Solution {
public:
    int mySqrt(int x) {
        long long result = 1;
        
        if(x == 0){
            return 0;
        }
        
        while(1){
            if(result * result > x){
                break;
            }
            result++;
        }
        
        return (int)result-1;
    }
};

 

 

이분탐색 이용하기 - 좀 더 빠르다.

mid = (s+e)/2 이지만 오버플로우를 피하기 위해 저렇게 계산한다.

class Solution {
public:
    int mySqrt(int x) {
        
        if(x == 0){
            return 0;
        }
        
        int s = 1, e = x;
        int result =1; 
        
        while(s<=e){
            int mid = s + (e-s)/2; // to avoid overflow
            
            if(mid <= x/mid){
                result = mid;
                s = mid +1;
            }else {
                e = mid - 1;
            }
        }
        
        return result;
    }
};

 

가장 빠른 방법!!!

이런 알고리즘도 존재한다.

 

바빌로니아 법 알고리즘

codingdog.tistory.com/entry/%EB%B0%94%EB%B9%8C%EB%A1%9C%EB%8B%88%EC%95%84-%EB%B2%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%96%B4%EB%96%BB%EA%B2%8C-sqrt-%ED%95%A8%EC%88%98%EB%A5%BC-%EA%B5%AC%ED%98%84%ED%95%A0%EA%B9%8C%EC%9A%94

바빌로니아 법 알고리즘 : 어떻게 sqrt 함수를 구현할까요?

별게 다 있다 뉴턴랩슨법을 활용한 알고리즘이라고 한다. 2차 방정식에서 접선들의 x절편 간격을 점차 줄여 해를 찾는 방식...이다.

 

암튼 식이 Xn = (Xn-1 + N/Xn-1) /2 이다. (Xn은 n번째 X, Xn-1은 n-1번째 X)

저 식을 여러번 돌리다보면 답이 나오는데 30번 안에 나오나보다,,???

암튼 아래 코드에선 n이 점차 작아져서 범위 안에 들어오면 break 시켰다.

class Solution {
public:
    int mySqrt(int x) {
        
        if(x == 0){
            return 0;
        }
        int result = 1; 
        long long n = 1;
        
        while(1){
            n = (n + x/n) /2;
            
            if(n*n <= x){
                result = n;
                break;
            }
            
        }
        return result;
    }
};