백준13706🐨제곱근

2 초 512 MB

문제

정수 N이 주어졌을 때, N의 제곱근을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다.

출력

첫째 줄에 정수 N의 제곱근을 출력한다.

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

예제 입력 3 복사

226576

예제 출력 3 복사

476

이 문제를 혹시나 하고 아래처럼 풀어보면 역시 오류가 난다.

print(int(int(open(0).read())**0.5))

런타임 에러 (OverflowError)

최대 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$니까 결국 2차곡선과 관계있다는 사실과 함께,

경사 하강법의 아이디어가 떠올랐다.

우리가 추측한 x에 대한 y값 위치의 미분값인 기울기를 통해 앞으로 갈지 뒤로갈지,

혹은 얼마나 갈 지도 알아낼 수 있을 것이고, 더 빨리 탐색할 수 있을 것 같았다. O(logN)보다 더.

그래서 이것 저것 찾아보다가

https://namu.wiki/w/%EB%89%B4%ED%84%B4-%EB%9E%A9%EC%8A%A8%20%EB%B0%A9%EB%B2%95

뉴턴-랩슨 방법

Newton–Raphson method 미분가능한 함수 에 대해 에 대한 방정식 의 근의 근삿값을 구하는

namu.wiki

이런 것을 찾았다. 경사하강법이랑 비슷한 느낌이다.

뉴턴-랩슨(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) $는 현재 추정값에서 함수의 기울기(미분값)입니다.

이 수식은 뉴턴-랩슨 방법을 사용하여 방정식의 근을 반복적으로 찾아가는 과정을 나타냅니다.

아래쪽 리스트도 라텍스 수식으로 표현하면 다음과 같습니다:

$$
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^2 = n )이 되는 ( 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}
  ]

뉴턴-랩슨 방법의 작동 방식

이 반복식을 이용해 제곱근을 찾는 과정을 따라가 봅시다.

초기값 설정: 먼저, ( x_0 )라는 초기 추정값을 설정합니다. 일반적으로 ( x_0 = n ) 또는 ( x_0 = \frac{n}{2} )와 같은 값으로 시작합니다.
반복 계산:
- 초기값 ( x_0 )에서 시작하여, 위의 반복식을 사용해 ( x_1, x_2, \ldots )를 점점 계산해 나갑니다.
- 각 단계에서 ( x_{k+1} )는 ( x_k )보다 더 정확한 제곱근에 가까워집니다.
수렴 조건: ( x_k )와 ( x_{k+1} )의 차이가 매우 작아질 때, 즉 우리가 원하는 정확도에 도달하면 반복을 멈추고 근사값을 출력합니다.

예제: 25의 제곱근을 구하기

뉴턴-랩슨 방법을 사용해 25의 제곱근을 구하는 예시를 살펴보겠습니다.

초기값 설정: ( x_0 = 25 )
반복 계산:
- 첫 번째 반복:
  [
  x_1 = \frac{x_0 + \frac{25}{x_0}}{2} = \frac{25 + \frac{25}{25}}{2} = \frac{25 + 1}{2} = 13
  ]
- 두 번째 반복:
  [
  x_2 = \frac{x_1 + \frac{25}{x_1}}{2} = \frac{13 + \frac{25}{13}}{2} \approx 7.46
  ]
- 세 번째 반복:
  [
  x_3 = \frac{x_2 + \frac{25}{x_2}}{2} = \frac{7.46 + \frac{25}{7.46}}{2} \approx 5.41
  ]
- 네 번째 반복:
  [
  x_4 = \frac{x_3 + \frac{25}{x_3}}{2} = \frac{5.41 + \frac{25}{5.41}}{2} \approx 5.01
  ]
- 다섯 번째 반복:
  [
  x_5 = \frac{x_4 + \frac{25}{x_4}}{2} = \frac{5.01 + \frac{25}{5.01}}{2} \approx 5.0
  ]

결국, 반복이 진행됨에 따라 ( x ) 값이 점점 더 정확한 제곱근 5에 가까워지는 것을 볼 수 있습니다.

뉴턴-랩슨 방법의 장점

빠른 수렴 속도: 이 방법은 근을 찾는 데 매우 빠르게 수렴합니다. 반복 횟수가 많지 않아도 원하는 정확도를 얻을 수 있습니다.
효율적: 다른 많은 근사 방법보다 더 효율적이며, 특히 복잡한 방정식을 푸는 데 유용합니다.

요약

뉴턴-랩슨 방법은 함수의 근을 찾는 반복적 알고리즘입니다. 접선의 기울기를 이용하여 점점 더 정확한 근을 찾아가는 방식으로, 제곱근을 구하는 문제뿐만 아니라 여러 수학적 문제를 푸는 데 사용할 수 있습니다. 이 방법의 핵심은 현재 추정값에서 함수의 값을 계산하고, 그것을 사용하여 더 나은 추정값을 찾는 반복적인 과정에 있습니다.

저작자표시 비영리 변경금지

붉은 각설탕