[백준] 제곱근(python)

백준, 제곱근

13706번: 제곱근

TL;DR

• 이진 탐색(Binary search)
• 수학(Mathematics)

문제 요약

1. 정수 N이 주어졌을 때, N의 제곱근을 구하는 프로그램을 작성하라.
2. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다.

 

- 제곱근을 구하는 문제이다. 문제만 봐서는 단순해보이지만 입력 제한을 살펴봐야 한다. 

- 입력은 항상 제곱근이 정수가 되는 값이 주어지고, 이 N의 최대 길이는 800자리이다. 즉, 엄청나게 큰 수가 입력이 될 수 있다.

입출력 형태

입출력 예시

 

- 입력에 대한 제곱근을 출력하면 된다.

풀이

보통의 경우 제곱근은 `math.sqrt`를 사용하거나 `** 0.5`를 사용해서 문제를 해결할 수 있다. 하지만 이 문제의 함정은 주어지는 숫자 N이 매우 큰 수라는 것이다.

컴퓨터공학/과학/전산학과에 입학하고 나면 컴퓨터에서 소수를 처리하는 방법인 부동 소수점(Floating point)를 배우게 된다. 컴퓨터의 소수를 표현하는 방법은 수학에서 사용하는 소수의 표현 방식과 상이하기 때문에 어느 정도 오차가 존재한다. 만약 보통의 경우에서 제곱근을 구하는 방식을 사용하면 매우 큰 수에 대해서는 제곱근을 계산한 후 다시 정수형 타입으로 변환하는 과정에서 이 오차가 발생한다.

 

10 ^ 80을 제곱했을 때의 값

 

그림에서 확인할 수 있듯이 10^2인 100에 대해서는 정확한 값을 보이지만 10^80에 대한 제곱근의 값은 10^40이 나와야 하지만 실제 계산된 값은 다른 값이 나온 것을 확인할 수 있다. 그렇기 때문에 이 문제는 보통의 경우로 풀었을 경우에는 오답이 난다.

 

그렇다면 어떻게 문제를 풀어야 할까 ? 문제 풀이의 힌트는 문제 속에 존재한다. 문제에서 주어지는 입력(N)은 항상 제곱근의 값이 정수가 되는 값으로 주어진다고 되어 있다. 이 말을 해석하면 1부터 N 사이에는 N의 제곱근이 존재한다는 뜻이 된다.

단순히 1부터 N까지 수를 1씩 증가시키며 완전 탐색을 진행하는 경우는 매우 큰 입력이 주어졌을 때 시간 초과가 날 수 있다. 1부터 N 사이의 수는 오름차순 정렬된 형태로 되어있기 때문에 Binary search를 쓰면 시간 초과 없이 문제를 해결할 수 있다.

import sys

N = int(sys.stdin.readline())
low, high = 1, N

while low <= high:
    mid = (low + high) // 2
    if mid ** 2 == N:
        print(mid)
        break
    elif mid ** 2 < N:
        low = mid + 1
    else:
        high = mid - 1

 

1부터 N 사이의 중간 지점을 찾아가며 해당 지점의 수를 제곱했을 때 N이 되는 경우를 찾으면 문제의 답을 얻을 수 있다.

다른 풀이

이 문제를 백준에서는 binary search와 수학으로 구분하고 있다. Binary search보다 수학적으로 접근했을 때 더 적은 시간으로 계산한 답이 존재한다. 다른 사람이 작성한 코드이고 어떻게 동작하는지 완전히 이해하지 못했기 때문에 별도로 포스팅하지는 않지만 이 문제를 푸는 사람들은 꼭 맞은 사람에 가서 시간이 가장 적게 걸린 이 분의 풀이를 확인하시면 좋을 것 같다.