[백준/13706] 제곱근 | 이진탐색

https://www.acmicpc.net/problem/13706

13706번: 제곱근

Heron's method(헤론 방법)

제곱근을 근사하는 방법이다. 이 방법은 대략적인 제곱근 값을 계산하고, 이를 시작점으로 반복적인 계산을 통해 값을 얻어낸다.

 

주어진 숫자 x의 제곱근을 구하는 방법

• x의 대략적인 제곱근 값을 구한다.(x/2)
• x를 x/2로 나눈다.
• x/2 + x(x/2): 이전 단계에서 구한 대략적인 제곱근 값과 그 역수의 합을 구한다.
• (x/2 + x(x/2)) / 2 : 이전 단계에서 구한 대략적인 제곱근 값과 그 역수의 평균값을 구한다.
• 이후 다시 2로 나누어서 더 나은 근사값을 구한다.

---

이진 탐색 기본 아이디어

적어도 처음과 끝 사이에서 검색 범위를 줄여 나가며 원하는 데이터를 찾는 알고리즘

1부터 100까지의 숫자 중 절반씩 배제하기 위해서는 반드시 정렬된 데이터로 이진 탐색을 실행해야 한다.

 

이 문제는 여러 개의 데이터 중 값을 찾아나가는 것이 아니라 하나의 데이터 연산을 통해 비슷한 값으로 수렴해 나가는 방식이다.

입력된 숫자와 1을 양끝점으로 잡아주고, 중간 지점부터 x값을 정하여 탐색을 시작한다.

가장 근사한 값이 나오면 반복문을 탈출하여 정답을 구한다.

---

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
l, r = 0, n

while l <= r:
    mid = (l+r)//2
    if mid ** 2 < n :
        l = mid + 1
    elif mid ** 2 > n :
        r = mid - 1
    else:
        ans = mid
        break

print(ans)