self.winter.(11). 회문(palindrome), 기하(절대/상대 오차의 허용), 에라토스테네스의 체 _ 백준 [1990, 15927, 11664]

🧐 에라토스테네스의 체   함수

def decimal(num):
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True​

for i in range(2, 100):
    if decimal(i):
        print(i, end = " ")​​

위의 과정을 통해 기존의 리스트에 누적하여 저장하는 방식보다 더욱 짧은 시간복잡도를 갖고 소수를 도출해 낼 수 있다.

 

🧐 회문 ( Palindrome )

회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.

이런 회문에 대한 구현을 파이썬은 다른 언어와 다르게 간단하게 구현할 수 있다는 점에서 단연 파이썬의 매력이 돋보인다.
다음과 같이 회문을 구현할 수 있다.

[숫자인 경우 회문인지 확인하는 법]

a, b = map(int,input().split())  

# a~b범위 사이 회문 모두 구하기
palindrome = [i for i in range(a,b+1) if str(i) == str(i)[::-1]]

 

[문자인 경우 회문인지 확인하는 법]

string = input()

if string == string[::-1]:
    print("palindrome")​

 

# a,b=map(int,input().split())
# print('%0.9f'%(a/b))  // 절대,상대오차는 소수점 9번째 자리(0.1e-9)까지 허용

 

🧐 절대오차, 상대오차의  표현 

백준을 풀다보면 위로 갈수록 수학, 기하문제의 경우 다음과 같은 내용을 보는 경우가 종종 있다.

이에 대해 어떤 방식으로 출력을 해야할 지 갑자기 막힐 수 있기에 이번기회에 짚고 넘어가고자 한다.



다만, 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 in range(b+1)]
dec_first = []
for i in range(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 = []
def palindrome(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 in range(a, b+1):
    palindrome(i)
ans.append(-1)
print(*ans, sep = "\n")

 

🤫  solution_1990

a, b = map(int,input().split())

def decimal(num):
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True


#10,000,000이상인 팰린드롬수는 존재 X
if b > 10000000 :
    b=10000000

palindrome = [i for i in range(a,b+1) if str(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 = 0
if string == string[::-1]:
    if string[:len(string) // 2 + 1] == string[:len(string) // 2 + 1][::-1]:
        ans = -1
    else:
        ans = len(string) - 1
else:
    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)/2
    l = ((ax-cx)**2+(ay-cy)**2+(az-cz)**2)**0.5
    h = ((mx-cx)**2+(my-cy)**2+(mz-cz)**2)**0.5
    r = ((bx-cx)**2+(by-cy)**2+(bz-cz)**2)**0.5

    if 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