[codeup] 3006. 완전 제곱수 찾기

https://codeup.kr/problem.php?id=3006

완전 제곱수 찾기

1. 문제

주어진 값보다 크지 않으며 가장 큰 완전 제곱수를 구하라.

2. 알고리즘

주어진 값의 제곱근을 구한 뒤, 소수점을 버린 후에 다시 제곱한다.

3. 주의할 점

sqrt를 사용하면 안된다. **는 써도 되겠지만 그러면 sqrt를 쓰지않는 의미가 없다. 따라서 제곱근을 수행하는 함수를 만들어야한다.

 

https://ko.wikipedia.org/wiki/%EB%B0%94%EB%B9%8C%EB%A1%9C%EB%8B%88%EC%95%84_%EB%B2%95

바빌로니아 법 - 위키백과, 우리 모두의 백과사전

여기서는 바빌로니아 법을 사용했다. 제곱근의 근사값을 구하는 알고리즘이다.

 

여기서는 초기값 X0의 값을 1로 잡았다.

 

또한, 컴퓨터에서의 2진수는 10진수만큼의 소수점을 표현하지 못하기 때문에 10진수로 계산해줘야한다. 여기서 사용할 수 있는 모듈이 decimal모듈이다. 

4. 소스코드

import decimal
# 입력 처리
k = int(input())
numbers = [decimal.Decimal(input()) for _ in range(k)]

# 사용할 상수 decimal로 정의
d1 = decimal.Decimal('1')
dhalf = decimal.Decimal('0.5')

# 바빌로니아 법을 이용한 제곱근 구현
def root(n):
    v = dhalf * (d1 + (n / d1))
    while True:
        compare = v
        v = dhalf * (v + (n / v))
        if abs(v - compare) < decimal.Decimal('0.000000000000000001'):
            break
    return v

# 제곱근 값을 int()로 소수점을 버리고 다시 제곱한 값을 반환
def psn(n):
    return int(root(n))**2

# 결과값 출력
for i in numbers:
    print(psn(i))