[백준] No.3783 세제곱근 01
3783번: 세제곱근
각 테스트 케이스에 대해서, 입력으로 주어진 수의 세제곱근을 소수점 10째짜리까지 출력한다. 이때, 반올림을 하는 것이 아니고, 버림을 해야 한다.
www.acmicpc.net
백준에는 solved.ac라는 랭크 시스템을 도입하여, 난이도를 책정한다.
동시에 내 랭크(티어) 지표를 나타내고, 다른 편리한 기능들도 많이 탑재하고 있다.
여러 기능 중에 '라이벌'이라는 기능이 있다.
다른 사람이 나를 라이벌로 지정하거나, 내가 다른 사람을 라이벌로 지정할 수 있다.
말이 라이벌이지 쉽게 말하면 즐겨찾기 기능이다.
종종 누군가 나를 라이벌로 지정했다 삭제하길 반복했었다.
그럴 때마다 '아, 내가 궁금해서 보러 와주었구나. 지금 열심히 하고 있구나'라는 생각이 들었다.
그리고 가장 최근(9월 10일)에 또 한 명이 나를 라이벌로 지정해주었다.
누구라고 특정지어 언급할 수는 없지만, 내게는 새로운 동기부여가 되었다.
문제 해결 수와 티어가 그 사람의 실력으로 직결되는 것은 아니다.
하지만 어려운 문제를 풀고 티어가 높을수록 이 사람이 열심히 노력했다는 것은 확인할 수 있다.
그리고 나를 추가한 라이벌은 골드 3에 170문제밖에 풀지 않았지만, 다이아 1문제와 플레 6문제를 푼 사람이었다.
오... 내가 코딩테스트 준비를 위해 백준에서 문제를 풀고 있지만, 그전에 한 사람의 개발자다.
개발자로서 상승하고 어려운 문제에 도전하려는 욕망은 언제나 가득 차있다.
맞다. 내가 코딩테스트를 준비하고 있지만, 중요한 것은 문제 해결 능력이다.
나도 마스터까지 가고 싶다. 지금 골드 문제를 푸는 것에 안주해서는 안 된다.
그리하여 저 분이 풀었던 문제들 중, 내가 풀 수 있는 게 무엇이 있을까?해서 처음으로 플레 문제를 도전하였다.
N의 세제곱근을 구하시오!라는 정말 간단한 설명의 문제를 선택했다.
와 정말 간단하다. 와 근데 어떻게 풀지?
당장 생각나는 방법은 2가지가 있다.
1. 이분 탐색으로 범위를 좁혀나간다.
2. 1/3 제곱을 한다.
두 가지 방식 모두 문제점이 있었다.
1. 정수가 아닌 소수인데, 소수는 무한하게 확장이 가능하다. 어디서 멈춰야 하지?
2. 1/3 제곱을 하면 소수로 저장할텐데, 정확도를 어떻게 구현해야하지?
def find_cube_root(right: int) -> float:
left = 0
count = 0
while left <= right:
if count == 1000:
return right
mid = (left + right) / 2
if mid ** 3 < N:
left = mid
count += 1
else:
right = mid
count += 1우선 이분 탐색으로 생각나는대로 작성했다.
예를 들어서 5의 세제곱근을 구한다고 가정해보자.
그럼 0부터 5까지 범위를 잡고, 중간값을 2.5로 둔다.
2.5의 세제곱은 15.625다. 그럼 범위를 작은 곳으로 좁혀야 한다. mid를 right에 넣자.
새롭게 0부터 2.5라는 범위가 생겼다. 다시 중간값을 구해 1.25로 둔다.
1.25의 세제곱은 1.953125다. 범위를 큰 곳으로 좁혀야 한다. mid를 left에 넣자.
이런 식으로 반복하는 방법으로 구현했다.
하지만 소수이기에 while left <= right가 조건문 밖으로 빠져나오는 경우는 없다.
0.0000...00001이라도 right가 클 테니까 말이다.
그래서 충분히 큰 수라고 생각이 드는 1000을 기준으로 횟수를 측정했다.
범위를 한 번 좁혀나갈 때마다 소수점 자릿수가 한 자리 길어진다.
아직 정수 부분이 충분히 크다면, 정수 자릿수가 한 자리씩 줄어든다.
입력 조건에서 '150 자리 이하'가 입력으로 주어진다고 했다.
그럼 정수가 150번 줄어들 수 있고, 소수는 최소 850자리까지 가질 수 있다.
세제곱근을 소수점 10째짜리까지 출력한다고 하니 넉넉하다고 생각했다.
Python3에서 되게 오랜만에 보는 에러다.
Python3는 <class 'int'>의 한계가 없지만, <class 'float'>의 한계는 존재한다.
IEEE 754를 따르는 Python float 구조상, 8byte를 가지고 최댓값은 약 1.8 * 1e308이다.
즉, 제곱이나 세제곱은 범위를 초과해버려 Overflow가 뜬다.
def find_cube_root(right: int) -> float:
left = 0
count = 0
try:
while left <= right:
if count == 1000:
return right
mid = (left + right) / 2
if mid ** 3 < N:
left = mid
count += 1
else:
right = mid
count += 1
except OverflowError:
return right이분탐색을 할 때, 어디서 Overflow가 뜨는지 수의 종류가 너무 광범위해 알기 어렵다.
그래서 try-except문으로 OverflowError가 뜨는 경우 right을 반환하게끔 코드를 변경해주었다.
그랬더니 Error도 아니고 WA가 떴다.
Python에서는 // 연산자가 아니라 / 연산자로 나온 결과는 언제나 <class 'float'>에 해당한다.
int와는 다르게 float는 8Byte로 범위가 제한되고, 그 값을 넘어가면 Overflow가 발생한다.
그렇게 입력이 일정 이상 커지면, 이분 탐색을 시작하자마자 mid ** 3에서 걸려버리고 만다.
정확하게는 103자리 이상의 숫자를 mid ** 3 연산을 하면 바로 right를 반환하게 된다.
즉, 세제곱근을 구한 게 아니라, 처음 값 그대로를 반환한 것이다.
(왜 103자리 이상인지 OverflowError에 대한 자세한 설명은 이 글을 참고하자.)
위의 그림은 IEEE754를 따르는 C++나 Java와 같은 4Byte float의 구조다.
Python은 흔히 말하는 double 자료형의 8Byte 소수 자료형이지만, 이는 중요하지 않다.
중요한 것은 소수를 저장하는 방식이다. 흔히 말하는 부동 소수점 방식이다.
부동 소수점은 '부호 비트', '지수 비트', '가수 비트'로 나누어 값을 저장한다.
이때 값을 저장하는 공간에 한계가 생겨 '오차'가 발생한다.
이를 대처하기 위해 Python에는 decimal이라는 라이브러리가 존재한다.
https://docs.python.org/ko/3/library/decimal.html#decimal.Context
https://docs.python.org/ko/3/library/decimal.html#decimal.Decimal
https://docs.python.org/ko/3/library/decimal.html#decimal.Decimal.quantize
decimal의 쓰임과 함수들은 위의 링크들을 참고하면 된다.
import decimal
decimal.getcontext().prec = 15
print(decimal.Decimal(1)) # 1
print(decimal.Decimal('1')) # 1
print(decimal.Decimal(3)) # 3
print(decimal.Decimal('3')) # 3
print(decimal.Decimal(1.1)) # 1.100000000000000088817841970012523233890533447265625
print(decimal.Decimal('1.1')) # 1.1
print(decimal.Decimal(1 / 3)) # 0.333333333333333314829616256247390992939472198486328125
print(decimal.Decimal(1) / decimal.Decimal(3)) # 0.333333333333333
print(decimal.Decimal('1') / decimal.Decimal('3')) # 0.333333333333333쉽게 말하면 demical 라이브러리는 '숫자를 10진수로 처리하여 정확한 소수점 자릿수를 표현할 때 사용'한다.
decimal.getcontext().prec = digits로 decimal 객체를 몇 번째 소수자리까지 지정할지 정할 수 있다.
만약 digits을 15로 지정했다면, decimal 객체의 소수는 소수점 아래 15번째자리까지 정확하게 표기한다.
decimal.Decimal(1)과 decimal.Decimal('1')을 출력해보면 둘의 결과는 동일하다.
물론 3과 '3'도 동일하다. 이는 정수이기 때문이다. 하지만 소수의 경우는 달라진다.
decimal.Decimal(1.1)은 1.1을 먼저 부동소수점 방식으로 저장한 뒤 Decimal로 만드는 코드다.
따라서 저장 결과는 일반적으로 1.1을 저장한 값과 동일하여, 뒤에 오차가 발생한다.
하지만 인수는 문자열 '1.1'로 주면 Decimal에서 오차가 없는 1.1로 저장한다.
이때 getcontext().prec = 15로 자릿수를 지정해주었는데 왜 1.100000000000000이 아니라 1.1일까?
getcontext().prec의 의미는 15번째자리까지 '오차가 없이 정확하게 하라'는 의미이다.
즉, 뒤에 붙은 0은 굳이 쓸 필요가 없는 것이다.
하나의 예시를 더 보면 decimal.Decimal(1/3)은 역시나 오차가 발생한다.
하지만 decimal.Decimal(value) / decimal.Decimal(value)로 계산한 경우 오차가 없다.
Context(
prec=28,
rounding=ROUND_HALF_EVEN,
Emin=-999999,
Emax=999999,
capitals=1,
clamp=0,
flags=[],
traps=[InvalidOperation, DivisionByZero, Overflow]
)context를 활용하여 몇 번째 소수자리까지 지정할지 정하는 코드가 있었다.
바로 위의 코드는 context의 세부 설정 사항들을 가져온 데이터이다.
기본 prec 자릿수는 28이다. 그리고 기본 반올림 방식은 ROUND_HALF_EVEN, 파이썬다운 오사오입이다.
참고로, decimal.max_prec로 최대 지정 자리를 확인할 수 있다. 최댓값은 100경 - 1이다.
# ---------- Import ----------
import decimal
decimal.getcontext().prec = 1000_0000이를 바탕으로 2번째 아이디어로 코드를 작성했다.
우선 넉넉하게 천만 자리까지 잡아주었다. 이 문제가 어느 정도의 정밀도를 요하는지 모르기 때문이다.
# ---------- Function ----------
decimal_num = decimal.Decimal(input_num)
pow_num = decimal.Decimal('1') / decimal.Decimal('3')
decimal_num = decimal.Decimal(decimal_num ** pow_num)숫자를 입력받고(decimal_num), 1/3 제곱을 할 숫자를 pow_num에 Decimal 객체로 계산해주었다.
그리고 decimal_num에 0.3333333... 제곱을 해주면 문제에서 구하고자하는 정답이 된다.
# ---------- Function ----------
decimal_num = round(decimal_num, 100_000)하지만 정답을 출력하기 전에 고려해야 하는 사항이 두 가지 있다.
1. INPUT ^ (1/3)이 정확하게 정수로 떨어지는 경우를 고려해야 한다.
예를 들어 INPUT(처음 입력한 decimal.Decimal(input_num) 값이 1000이라고 가정해보자.
1000의 세제곱근은 당연히 10이다. 하지만 여기서 1/3 제곱을 해주었기에 9.999999...가 된다.
즉, 반올림을 할 필요가 있다.
반올림을 할 때 소수점 10째자리까지 영향이 미치지 않게끔 적당히 낮은 자리에서 반올림했다.
# ---------- Function ----------
decimal_num = decimal.Decimal(decimal_num)\
.quantize(
decimal.Decimal('.0000000000'),
rounding=decimal.ROUND_DOWN
)2. 세제곱근을 소수점 10째짜리까지 출력한다. 이때, 반올림을 하는 것이 아니고, 버림을 해야 한다.
처음에 소수점 아래 천만 자리까지 값을 구해주었기 때문에, 10번째에서 버림해야 한다.
이는 Decimal의 quantize 함수로 해결할 수 있다.
└ https://docs.python.org/ko/3/library/decimal.html#decimal.Decimal.quantize
첫 번째 매개변수(exp)는 계산하려는 자릿수를 지정해준다.
두 번째 매개변수(rounding)은 반올림을 어떤 방식으로 할지 지정해준다.
'.0000000000'이라는 값을 넣어 10번째 자리까지 계산하게 했으며, ROUND_DOWN으로 버려주었다.
그랬더니, 그제서야 AC를 받았다...
처음으로 푼 플래티넘 문제다. 뭔가 막 감격스러울 줄 알았는데 그정도까지는 아니었다.
다른 문제와 똑같이 내가 해결했다는 뿌듯함이 있는데, 이게 조금 더 크다?
그래도 처음으로 플래 문제를 푼 의미있는 날이다.
처음에 prec()로 자리를 지정해주고, 중간에 round()로 반올림해주었다.
각각 천만, 십만이라는 임의의 값을 넣었는데, 이 문제에서 정확한 경계는 어디일까 궁금해졌다.
그래서 위의 사진은 경계를 알아내기 위해, 이분 탐색(?)으로 수를 좁혀가며 시도한 흔적이다.
# ---------- Import ----------
import decimal
decimal.getcontext().prec = 153
# ---------- Function ----------
def cube_root(input_num):
decimal_num = decimal.Decimal(input_num)
pow_num = decimal.Decimal('1') / decimal.Decimal('3')
decimal_num = decimal.Decimal(decimal_num ** pow_num)
decimal_num = round(decimal_num, 101)
decimal_num = decimal.Decimal(decimal_num)\
.quantize(
decimal.Decimal('.0000000000'),
rounding=decimal.ROUND_DOWN
)
return decimal_num결국 이 문제에서는 prec는 153자리, 반올림은 101자리까지 정답을 받을 수 있다.
어떤 테스트 케이스가 있기 때문에 이런 숫자가 나오는지는 모르겠다.
테스트 케이스가 무엇이 있는지도 알 수 있으면 좋겠다는 생각이 다시금 드는 문제다.