백준을 풀다보면 위로 갈수록 수학, 기하문제의 경우 다음과 같은 내용을 보는 경우가 종종 있다.
이에 대해 어떤 방식으로 출력을 해야할 지 갑자기 막힐 수 있기에 이번기회에 짚고 넘어가고자 한다.
다만, 10^-9 이하의 오차를 허용한다는 말이 꼭 소수 9번째자리까지만 출력하라는 것은 아니다. 예로 백준1008번을 예로 들겠다. 소수점 9번째자리 보여주는 방법은 아래와 같다.
a, b = map(float,input().split())
print('%0.9f'%(a/b)) // 절대,상대오차는 소수점 9번째 자리(0.1e-9)까지 허용
소숫점 앞의 숫자는 전체 길이를 정한 문자열 공간 수를 의미함( 0은 정하지 않음을 의미 )
소숫점('.')뒤의 숫자9는 소숫점 뒤에 나올 숫자의 개수를 의미함
<자주쓰는 문자열 포맷 코드 종류 >
%s: 문자열(string)
%c: 문자 1개 (character)
%d:정수(integer)
%f:부동소수(floating- point)
%%: 문자 %자체
🧐 백준 1990 (소수인 회문) Gold V
🤫solution_1990(시간초과)
import math, sys
input = sys.stdin.readline
a, b = map(int, input().split())
dec = [i for i inrange(b+1)]
dec_first = []
for i inrange(2, int(b**0.5) + 1):
if i in dec:
dec_first.append(i)
dec = [j for j in dec if j%i != 0]
decimal = dec_first + dec
ans = []
defpalindrome(num):
string_num = str(num)
num_len = len(string_num)
if string_num[:num_len // 2] == string_num[math.ceil(num_len / 2):][::-1]:
if num in decimal:
ans.append(num)
for i inrange(a, b+1):
palindrome(i)
ans.append(-1)
print(*ans, sep = "\n")
🤫solution_1990
a, b = map(int,input().split())
defdecimal(num):for i inrange(2, int(num**0.5) + 1):
if num % i == 0:
returnFalsereturnTrue#10,000,000이상인 팰린드롬수는 존재 Xif b > 10000000 :
b=10000000
palindrome = [i for i inrange(a,b+1) ifstr(i) == str(i)[::-1]]
for i in palindrome:
if decimal(i):
print(i)
print(-1)
🧐 백준 15927 (회문은 회문이 아니야!) Gold V
🤫Algorithm
1) 문자열 전체가 회문이 아니면 답은 문자열의 길이이다.
2) 문자열 전체가 회문일 때,
i) 문자열 전체가 모두 같은 문자일 때 팰린드롬이 아닌 부분 문자열이 존재하지 않기에 답은 -1이다.
ii) 처음 또는 끝의 문자 하나만 제외한 문자열은 팰린드롬이 아니기에 답은 (원래 문자열의 길이 - 1)이다.
🤫solution_15927
string = input()
ans = 0ifstring == string[::-1]:
ifstring[:len(string) // 2 + 1] == string[:len(string) // 2 + 1][::-1]:
ans = -1else:
ans = len(string) - 1else:
ans = len(string)
print(ans)
🧐 백준 11664 (CCW, 외적) Gold V
🤫Algorithm
# 점 a를 선분의 왼쪽에 있는 점, 점 b를 선분의 오른쪽에 있는 점이라 하자.# 점 a와 점 b의 중간점 m을 구한다.# l = 점 a와 점 c의 거리# r = 점 b와 점 c의 거리# h = 점 m과 점 c의 거리# 만약 h가 현재 존재하는 최소값 ans보다 작다면, ans를 h로 갱신해줍니다.# 만약 l이 r보다 크다면, c가 a보다 b에 더 가깝게 있다는 뜻이므로 점 a를 점 m으로 바꿔준다.# (이분탐색을 진행해야 하므로 더 가까운 쪽으로 범위를 좁혀줘야 하기 때문.)# 반대로 r이 l보다 크다면 c가 b보다 a에 더 가깝게 있다는 뜻이므로 점 b를 점 m으로 바꿔준다.
🤫solution_11664
ax,ay,az,bx,by,bz,cx,cy,cz = map(int,input().split())
ans = float('inf')
while True:
mx,my,mz = (ax+bx)/2,(ay+by)/2,(az+bz)/2l = ((ax-cx)**2+(ay-cy)**2+(az-cz)**2)**0.5h = ((mx-cx)**2+(my-cy)**2+(mz-cz)**2)**0.5r = ((bx-cx)**2+(by-cy)**2+(bz-cz)**2)**0.5if abs(ans-h) <= 1e-6:
print('%0.10f'%ans)
exit()
if h < ans:
ans = h
if l > r:
ax,ay,az = mx,my,mz
else:
bx,by,bz = mx,my,mz
🤔 Algorithm 과정 1. num이라는 빈 리스트에 입력된 M ~ N까지의 숫자를 넣는다. 2. 약수의 개수를 세는 cnt라는 변수를 선언, 0으로 초기화한다. 3. 소수를 담을 리스트 dec을 선언한다. 4. num리스트의 원소를 차례로 돌면서 i % j == 0 즉, 약수일 때, cnt값을 증가시킨다. 5. 이렇게 약수의 개수가 담긴 cnt변수에 대해 만약 약수의 개수가 2개라면(cnt == 2) 소수인것! 따라서 소수라면 dec 리스트에 원소를 추가해주고 cnt==0이라면 소수가 없는 것이므로 0을 출력!
🤫solution_2581
M, N = int(input()), int(input())
num = []
for i inrange(N-M+1):
num.append(i+M)
dec = []
for i in num:
cnt = 0for j inrange(1, i+1):
if i % j == 0:
cnt += 1if cnt == 2:
dec.append(i)
iflen(dec) == 0:
print(-1)
else:
print(sum(dec))
print(min(dec))
🧐 백준 1929 (에라토스테네스의 체) _ 앞으로 계속 이 문제에서 파생하여 문항을 해결함
🤫해결의 실마리
🤔 에라토스테네스의 체 (Sieve of Eratosthenes)
에라토스테네스의 체 원리는 다음과 같다. 1. 소수가 아닌 1을 지운다. 2. 2의 배수를 지운다. 3. 앞서 지운 2의 배수가 아닌 것들 중 최소값인 3의 배수를 지운다. 4. 앞서 지운 2, 3의 배수가 아닌 값들 중 최소값인 5의 배수를 지운다. 5. 이 과정을 반복하여 걸러지는 것들이 비로소 소수가 된다. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 이러한 에라토스테네스의 체는 "특정 구간이 주어졌을 때" 매우 빠르게 소수를 도출할 수 있다. 위의 2581번처럼 풀면 시간복잡도는 O(n)으로 비교적 시간이 오래 걸린다. 하지만 에라토스테네스의 체의 시간복잡도는 O(nlog(log n))으로 매우 빠르게 도출이 가능하다. 또한 약수의 경우, 2*4, 4*2 처럼 반복이 되기 때문에 가장 중요한 것은 범위의 마지막 수의 루트 값까지만 반복함으로 시간을 더욱 줄일 수 있다!
🤔Algorithm 과정 알고리즘과정은 위에서 설명하는 에라토스테네스의 방식을 차용하였다. 또한 코드에 대한 설명은 아래 그림으로 대체하겠다.
🤫solution_1929
m, n = map(int, input().split())
num = [i for i inrange(max(2, m), n+1)] # m ~ n사이 숫자를 넣은 리스트 (단, 1은 제외)
dec_sqr_n = [] # n의 제곱근까지의 범위안에서 소수를 집어 넣을 리스트for i inrange(2, int(n**0.5) + 1): # 2에서 n의 제곱근까지만 반복if i in num:
dec_sqr_n.append(i)
num = [j for j in num if j % i != 0]
print(*(dec_sqr_n + num), sep = "\n")
🧐 백준 4948 (에라토스테네스의 체)
🤫해결의 실마리
🤔에라토스테네스의 체(Sieve of Eratosthenes) 🤔Algorithm 과정 위 1929와 거의 동일한 방식으로 풀었지만 방법은 다음과 같다. 1. n의 범위 사이의 자연수를 저장하는 num 리스트를 생성한다. (1 ≤ n ≤ 123456) 2. 리스트 num을 1929번 풀이처럼 소수만 존재하도록 만들어준다. 3. 1929와 같은 방식으로 n의 범위사이에 존재하는 모든 소수가 담긴 decimal이라는 리스트를 생성해준다. 4. 0이 들어오기 전까지 while문을 이용해 입력을 받아주고 5. decimal 리스트에서 입력의 범위에 해당하는 값들의 개수를 세어 출력해준다.
🤫solution_4948 (시간초과)
defdecimal(N):
n = N+1
num = [i for i inrange(n, 2*N + 1)]
dec_half = []
for i inrange(2, int((2*N)**0.5) + 1):
if i in num:
dec_half.append(i)
num = [j for j in num if j % i != 0]
returnlen(dec_half+num)
num = -1whileTrue:
num = int(input())
if num == 0:
breakelse:
print(decimal(num))
처음 짠 코드로 1929와 비슷하게 함수를 생성하여 풀었으나 시간초과가 발생하였다. 시간복잡도를 염두하지 않고머리를 장식으로 두고 문제에 접근한 결과라 생각할 수 밖에 없다. 함수에서 2중 for문을 사용한 것을 while문에서 계속 받으니 그럴 수 밖에...
🤫solution_4948
from math import sqrt
# 1 <= n <= 123456 사이 자연수를 담은 리스트 생성
num = [i for i inrange(2, 123456 * 2)]
# 리스트 num을 이전처럼 소수만 있게 만들어주기.
dec_half = []
for i inrange(2, int(sqrt(123456*2)) + 1):
if i in num:
dec_half.append(i)
num = [j for j in num if j%i != 0]
decimal = dec_half + num
n = -1whileTrue:
n = int(input())
if n == 0:
break# decimal 리스트에서 입력의 범위에 해당하는 값들의 개수를 세어 출력print(len([i for i in decimal if n < i <= 2*n]))
🧐 백준 9020 (에라토스테네스의 체)
🤫해결의 실마리
🤔에라토스테네스의 체(Sieve of Eratosthenes) 🤔Algorithm 과정 두 소수의 차이가 가장 작은 것의 의미를 생각해보면 다음과 같다. 소수간의 차이가 작을수록 최대값의 절반과 가까워진다! 16으 예로 들자면 다음과 같다. [3, 13], [5, 11] => 3 5 (8) 11 13
따라서 핵심은 시간초과가 걸리지 않으려면 소수의 절반만 훑어야 한다.
🤫solution_9020 (시간초과)
T = int(input())
n = [int(input()) for _ inrange(T)]
num = [i for i inrange(2, 10001)]
dec_half = []
for i inrange(2, 100 + 1):
if i in num:
dec_half.append(i)
num = [j for j in num if j % i != 0]
decimal = dec_half + num
for i in n:
dec = []
for j inrange(len(decimal)):
for k inrange(j, len(decimal)):
if i == decimal[j] + decimal[k]:
dec.append([decimal[j], decimal[k]])
print(*dec[-1])
처음 짠 코드로 문제점은 소수의 전체를 계속 훑으면서 비교를 진행하기 때문에 위의 알고리즘보다 2배 이상의 시간이 걸릴 가능성이 높다. 먼저 위의 코드를 짠 과정은 다음과 같다. 1. 먼저 범위에 해당하는 모든 소수를 담는 리스트를 생성하고 2. 그 리스트 안에서 두 소수간의 덧셈이 입력값과 동일한 것을 찾아서 dec이라는 리스트에 넣는다. 3. dec에는 [[3, 5]], [[3, 7], [5, 5]], [[3, 13], [5, 11]] 처럼 들어간 것이므로 4. 각 리스트의 마지막 인덱스에 해당하는 리스트가 차이가 가장 작은 소수 리스트인것. 이를 for문을 이용해 출력하였다.
🤫solution_9020
num = [i for i inrange(2, 10000 + 1)]
dec_half = []
for i inrange(2, 100 + 1):
if i in num:
dec_half.append(i)
num = [j for j in num if j%i != 0]
decimal = dec_half + num
T = int(input())
for i inrange(T):
n = int(input())
n_half = n // 2for j inrange(n_half, 1, -1):
if j indecimaland n - j indecimal:
print(j, n - j)
break
