2초 512MB
문제
정수 N이 주어졌을 때, N의 제곱근을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다.
출력
첫째 줄에 정수 N의 제곱근을 출력한다.
예제 입력 1
36
예제 출력 1
6
예제 입력 2
81
예제 출력 2
9
예제 입력 3
226576
예제 출력 3
476
이 문제를 아래처럼 풀어보면 오류가 발생한다:
print(int(int(open(0).read())**0.5))최대 800자리이기 때문에 발생하는 오류이다.
그래서 math 모듈을 사용해 보자. integer sqrt 함수가 있다.
import math
print(int(math.isqrt(int(open(0).read()))))40ms로 통과.
하지만 이 문제는 이분탐색 연습 문제집에 있었다.
n = int(open(0).read())
left, right = 0, n
while left <= right:
mid = (left + right) >> 1
q = mid * mid
if q == n:
print(mid)
exit()
elif q > n:
right = mid - 1
else:
left = mid + 1이 코드도 40ms가 걸린다.
이분탐색은 추측한 값이 더 큰지 작은지를 통해 앞쪽 절반을 탐색할지 뒤쪽 절반을 탐색할지를 정하는 것이다. 그런데 문득 제곱근이니까 $n=x^2$와 관계가 있다는 사실과 함께 경사 하강법의 아이디어가 떠올랐다.
우리가 추측한 x에 대한 y값 위치의 미분값인 기울기를 통해 앞으로 갈지 뒤로 갈지, 혹은 얼마나 갈지도 알 수 있을 것이고, 더 빨리 탐색할 수 있을 것 같았다. O(logN)보다 더.
그래서 찾아보다가 뉴턴-랩슨 방법을 발견했다. 경사하강법과 비슷한 느낌이다.
뉴턴-랩슨(Newton-Raphson) 방법은 방정식의 근을 찾기 위해 사용하는 반복적인 알고리즘이다. 쉽게 말해서, 어떤 함수가 0이 되는 점(근)을 빠르게 찾는 방법이다.
예를 들어, 우리가 어떤 수 $n$의 제곱근을 구하고 싶다면, 이를 수학적으로 표현하면 $x^2 = n$을 만족하는 $x$를 찾는 문제이다. 뉴턴-랩슨 방법은 이 문제를 반복적으로 해결하여 근사값을 구한다.
뉴턴-랩슨 방법의 기본 개념
- 기본 아이디어:
뉴턴-랩슨 방법은 함수의 그래프와 x축이 만나는 점, 즉 함수가 0이 되는 점을 찾는 것이다. 이를 위해 현재 위치에서의 기울기(접선)를 이용하여 함수가 0이 되는 위치를 점점 더 가까이 찾아간다. - 접선의 기울기 이용:
함수 $f(x)$가 있을 때, 우리는 $f(x) = 0$이 되는 $x$의 값을 찾고자 한다. 현재 위치 $x_k$에서 함수 $f(x)$의 값을 계산하고, 접선을 그린 후 그 접선이 x축과 만나는 새로운 점 $x_{k+1}$을 찾는다. 이를 반복하면 점점 더 정확한 근을 찾을 수 있다.
뉴턴-랩슨 방법의 반복식
뉴턴-랩슨 방법의 핵심은 반복식이다. 이 반복식은 다음과 같다:
$$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$$
여기서:
- $x_k$는 현재 추정값이다.
- $x_{k+1}$는 다음 추정값이다.
- $f(x_k)$는 현재 추정값에서 함수의 값이다.
- $f'(x_k)$는 현재 추정값에서 함수의 기울기(미분값)이다.
제곱근 예시로 이해하기
제곱근을 구하는 문제로 뉴턴-랩슨 방법을 적용해 보자. 우리가 구하려는 것은 어떤 수 $n$의 제곱근 $x$이다. 즉, $x^2 = n$을 만족하는 $x$를 찾고자 한다.
- 함수 정의:
우리가 찾고자 하는 제곱근을 $x$라고 하면, 이를 풀기 위한 함수 $f(x)$를 다음과 같이 정의할 수 있다: $$f(x) = x^2 - n$$ 우리는 이 함수가 0이 되는 $x$를 찾고자 한다. - 함수의 미분:
이 함수의 미분은 다음과 같다: $$f'(x) = 2x$$ - 반복식 적용:
뉴턴-랩슨 방법의 반복식을 적용하면 다음과 같다: $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{x_k^2 - n}{2x_k}$$ 이를 단순화하면: $$x_{k+1} = \frac{x_k + \frac{n}{x_k}}{2}$$
https://namu.wiki/w/%EB%B0%94%EB%B9%8C%EB%A1%9C%EB%8B%88%EC%95%84%EB%B2%95
바빌로니아법
바빌로니아 법(Babylonian method) 또는 헤론법(Heron's method)은 제곱근 에 대한 근사값
namu.wiki
바빌로니아 법 (Babylonian Method)
바빌로니아 법(Babylonian method) 또는 헤론법(Heron's method)은 제곱근에 대한 근사값을 구하는 알고리즘이다. 이 방법은 뉴턴-랩슨 방법의 제곱근 버전이라고 할 수 있다.
바빌로니아 법의 기본 아이디어는 다음과 같다:
- 초기값 설정: 어떤 수 $n$의 제곱근을 구하고자 할 때, 먼저 초기 추정값 $x_0$을 설정한다. 일반적으로 $x_0 = n$ 또는 $x_0 = \frac{n}{2}$로 시작한다.
- 반복 계산: 초기값에서 시작하여, 다음 반복식을 사용해 점점 더 정확한 근사값을 구한다:
$$x_{k+1} = \frac{x_k + \frac{n}{x_k}}{2}$$ - 이 과정을 원하는 정확도에 도달할 때까지 반복한다. 반복이 진행될수록 $x_k$는 점점 더 정확한 제곱근에 가까워진다.
바빌로니아 법은 뉴턴-랩슨 방법과 유사하지만, 제곱근을 구하는 문제에 특화되어 있다. 이 방법 역시 매우 빠르게 수렴하며, 적은 반복 횟수로도 높은 정확도를 얻을 수 있다.
예제: 25의 제곱근을 바빌로니아 법으로 구하기
바빌로니아 법을 사용해 25의 제곱근을 구하는 예시를 살펴보자.
- 초기값 설정: $x_0 = 25$
- 반복 계산:
- 첫 번째 반복: $$x_1 = \frac{x_0 + \frac{25}{x_0}}{2} = \frac{25 + 1}{2} = 13$$
- 두 번째 반복: $$x_2 = \frac{x_1 + \frac{25}{x_1}}{2} \approx 7.46$$
- 세 번째 반복: $$x_3 = \frac{x_2 + \frac{25}{x_2}}{2} \approx 5.41$$
- 네 번째 반복: $$x_4 = \frac{x_3 + \frac{25}{x_3}}{2} \approx 5.01$$
- 다섯 번째 반복: $$x_5 = \frac{x_4 + \frac{25}{x_4}}{2} \approx 5.0$$
결국, 반복이 진행됨에 따라 $x$ 값이 점점 더 정확한 제곱근 5에 가까워지는 것을 볼 수 있다.
뉴턴-랩슨 방법의 장점
- 빠른 수렴 속도: 이 방법은 근을 찾는 데 매우 빠르게 수렴한다. 반복 횟수가 많지 않아도 원하는 정확도를 얻을 수 있다.
- 효율적: 다른 많은 근사 방법보다 더 효율적이며, 특히 복잡한 방정식을 푸는 데 유용하다.
요약
뉴턴-랩슨 방법과 바빌로니아 법은 함수의 근을 찾는 반복적 알고리즘이다. 뉴턴-랩슨 방법은 접선의 기울기를 이용하여 점점 더 정확한 근을 찾아가는 방식이며, 바빌로니아 법은 제곱근을 구하는 문제에 특화된 방법이다. 두 방법 모두 매우 빠르게 수렴하며, 다양한 수학적 문제를 푸는 데 사용할 수 있다. 이 방법들의 핵심은 현재 추정값에서 함수의 값을 계산하고, 그것을 사용하여 더 나은 추정값을 찾는 반복적인 과정에 있다.
https://www.youtube.com/watch?v=HWdvH_rjVm0
바빌로니아 법 알고리즘 : 어떻게 sqrt 함수를 구현할까요?
sqrt를 어떻게 계산하면 좋을까요? 사실 어셈블리 명령에 fsqrt가 있긴 합니다. 그리고 추후에, 오늘 설명한 방법하고 Compare를 해 볼 겁니다. 우리는 sqrt(k)의 값을 구하는 것이 목표입니다. 어떻게
codingdog.tistory.com
