Leetcode 문제 69번 Sqrt(x)

문제 출처:https://leetcode.com/problems/sqrtx/

Sqrt(x) - LeetCode

Leetcode 69번 문제 Sqrt(x)

---

문제 분석

처음에는 ${\sqrt{x}}$를 어떻게 풀 수 있을지 답이 안섰습니다. 그저 1부터 ${\frac{x}{2}}$까지 본다면, 시간복잡도는 ${O(\frac{2^{31}-1}{2})}$가 될 것이 뻔했기 때문입니다. 그래서 구글에 검색해보았고 저는 괜찮은 방법을 찾을 수 있었습니다.

 

[C/C++] math.h sqrt() 함수 구현

이 블로그를 통해 Babylonian가 무엇인지 알게 되었습니다.

바빌로니아 법 

바빌로니아 법(The Babylonian Method)은 임의의 수의 제곱근에 빠르게 수렴하는 수열을 만들어 근삿값을 구하는 방법이다. 뉴턴랩슨 법을 이용하여 이차방정식의 근사해를 구하는 것과 유사하다. 헤론의 저서에서 바빌로니아 법과 비슷한 형태의 풀이가 제시되었기 때문에 바빌로니아 법을 헤론의 제곱근 풀이법이라고 하기도 한다.

양의 실수 a에 대하여 다음 과정을 따라 ${\sqrt{a}}$의 근삿값을 구할 수 있다.
1. 임의의 양의 실수 ${x_0}$를 택한다. 이 값이 ${\sqrt{a}}$에 가까울수록 더 빨리 근삿값을 구할 수 있다.
2. ${{x_{n+1}} = {\frac{1}{2}(x_n + \frac{a}{x_n})} = {\frac{{x_{n}}^{2} + a}{2x_n}}}$
3. 원하는 정밀도에 이르기까지 2의 과정을 반복.
출처 : https://has3ong.tistory.com/71

---

코드는 다음과 같습니다:

class Solution {
public:
    int mySqrt(int x) {
        //Babylonian method
        double n = 10.0;
        for(int i = 0; i < 100; i++)
            n = (n + (x / n)) / 2;
        return n;    
    }
};

빠르게 통과했다.

---

해당 문제는 Github에서도 보실 수 있습니다:

https://github.com/gurcks8989/CodingTest/blob/master/LeetCode/P69_Sqrt(x).cpp 

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든 환영입니다.