백준 2417번 정수 제곱근 파이썬 - 부동소수점

문제

정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오.

 

문제해설

본 문제는, 입력 숫자가 2의 63승이다.

"문제만 본다면, 그냥 math.sqrt나 **0.5로 제곱근을 구해주면 안되나 ?"

라고 생각할 수도 있지만, 큰 오산이다.

 

아마 위와 같은 방법으로 계산을 해보면, 반드시 더 작은 숫자가 나올 것이다.

이는 컴퓨터가 사용하는 숫자 표현 방식에 의거한다.

 

이를 이해하기 위해선 부동소수점이라는 개념을 알아야 한다.

부동 소수점이란, 컴퓨터가 실수를 표현하는 방법이다.

주로 IEEE 754라고 하는게 부동소수점을 표현하는 표준 규칙이다.

 

간략하게 설명하자면, 실수를 64비트나 32비트로 표현한다.

 

그리고 실수로 표현하기 위해 각 비트를 3개의 종류로 나눈다.

 

부호비트, 지수비트, 가수비트이다.

 

각각 숫자의 양과 음을 나타내는 부호비트,

지수가 어떻게 이동했는지(소수점의 위치)를 나타내는 지수비트,

그리고 마지막으로 소수점을 이동한 뒤의 유효 숫자(실수 부분)를 나타내는 가수비트이다.

 

이 때, 컴퓨터의 제한적인 비트로 표현가능한 범위가 넘어가면 수의 손실이 발생한다.

 

대부분의 숫자는 무한소수로 표현될 수 있으나,

컴퓨터의 메모리 공간은 제한되어 있기에 이를 모두 표현할 수 없다.

 

따라서 이 때, 컴퓨터는 이를 근사치로 표현한다.

근사치이므로 어느정도 실제 값과 오차가 발생한다는 점이다.

 

이 문제를 그렇기 때문에 간단히 해결할 수 없다.

 

다시 문제를 살펴보면, 문제의 입력값 범위가 말이 안된다는 것을 알 수 있다.

 

대부분 이러한 경우, 이진탐색을 사용해주면 된다.

 

또한, 오차로 인해 값이 작아지므로, 이진탐색에서 mid값을 비교하지 않고,

start의 값을 통해 이를 확인해주면 된다.

 

이를 위해서 이진탐색을 재귀함수가 아니라 while문으로 구현했다.

 

코드는 아래와 같다.

 

n = int(input())

start, end = 0, n

while start <= end:
    mid = (start + end) // 2

    if mid**2 < n:
        start = mid + 1
    else:
        end = mid - 1

print(start)