LeetCode (13) - Sqrt(x)(파이썬, python)

❓ 문제

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.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

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 <= 231 - 1

---

Given Code

class Solution:
    def mySqrt(self, x: int) -> int:
        

---

내 풀이 (1트)

class Solution:
    def mySqrt(self, x: int) -> int:
        res = 0
        while 0 > (res + 1)**2 - x - 1:
            res += 1
        return res

역시나 처음부터 쭉쭉 올라가면 안된다…(시간 초과) 뉴턴 메소드 같은걸 써야하나… 생각하면서 제곱근을 찾는 알고리즘을 찾아봤는데 바빌로니아 법이라는게 있더군요

---

내 풀이 (2트, 바빌로니아 법)

근데 이게 어디서 튀어나왔는지, 믿을만한것인지 모르겠어서 원리를 파악해봤습니다.

k에 대한 제곱근은 f(x) = x^2 - k 의 해 입니다.

Newton’s methods와 역시 연관이 있더군요.여길 참조하세요 (https://ko.wikipedia.org/wiki/%EB%89%B4%ED%84%B4_%EB%B0%A9%EB%B2%95)

x_(t+1) = x_t - f(x) / 2(f’(x))

와

f’(x) = 2x

를 이용해

x_(t+1) = x_t - f(x) / 2(f’(x)) = x_t - (x_t^2 - k)/(2x_t) = (1/2)(x_t + k/x_t) 를 확인했습니다.

이제 이거 적절히 반복해주면 될거같네요!