[백준 BOJ] 단계별로 문제풀기 - 기본수학 2 정답 및 후기(파이썬, python)

백준 알고리즘에서 제공되는 문제들 중 단계별로 문제 풀기 - 기본 수학 2를 파이썬으로 풀어보았다. 코드는 11문제 통째로 깃허브에 올려놓았으며 각 문제마다 주석으로 표시해놨다.

 

https://www.acmicpc.net/step/10

기본 수학 2 단계

원본 코드는 깃허브에!

https://github.com/tomy9729/Algorithm/blob/master/BaekJoon/Step-by-step%20troubleshooting(%EB%8B%A8%EA%B3%84%EB%B3%84%EB%A1%9C%20%EB%AC%B8%EC%A0%9C%ED%92%80%EA%B8%B0)/%EB%B0%B1%EC%A4%80_%EB%8B%A8%EA%B3%84%EB%B3%84%EB%A1%9C%EB%AC%B8%EC%A0%9C%ED%92%80%EA%B8%B0_%EA%B8%B0%EB%B3%B8%EC%88%98%ED%95%991%2C2.py

tomy9729/Algorithm

0. 전체 후기

전체적으로 크게 어려운 문제는 없었으며 수학적인 것도 중등 수학 정도의 난이도이다. 마지막 터렛 문제에서 경우의 수를 나누기 위해 그림 그려가며 푼 거 빼고는 오래 걸리지 않았다. 중간중간 수학을 글로만 설명해서 "이게 뭔 말이야?" 싶은 문제도 있었지만 조금만 생각해보면 충분히 이해할 수 있을 정도의 난이도였다.

 

1. 11653번 소인수분해

소인수분해 개념 자체는 어렵지 않았다. 조금 특이점이 있다면 반복문을 두 번 쓰기 싫어서 재귀 함수로 풀었다.

#11653번 소인수분해
import math
n = int(input())

def factorization(m) :  
  for i in range(2,m+1):
     if m % i == 0:
       print(i)
       l = m // i
       if l == 1 : break
       factorization(l)
       break

factorization(n)

 

2. 1929번 소수 구하기

이 문제부터는 소수를 구할 때 에라토스테네스의 체를 이용하여 코드를 작성했다. 소수 관련 문제에서 시간 초과를 회피하기 위 헤서는 에라토스테네스의 체를 이용하는 것이 필수이다.

#1929번 소수구하기
m,n = input().split()
m = int(m)
n = int(n)
arr = [True]*(n+1)
arr[1] = False
def is_prime_num(m,n) : 
  for i in range(2,n) : 
    j = 2
    while i*j <= n : 
      l = i*j
      arr[l] = False
      j += 1
      
is_prime_num(m,n)
for i in range(m,n+1) : 
  if arr[i] : print(i)

 

3. 4948번 베르트랑 공준

소수 구하기 문제와 비교해서 비슷하지만 범위 설정에 주의할 필요가 있다.

#4948번 베르트랑 공준

def is_prime_num(n) :
  for i in range(2,int((2*n)**0.5)+1):
      for j in range(2*i, 2*n+1, i):
          arr[j] = False

n = int(input())
while n != 0 : 
  arr = [False,False] + [True]*(2*n+1)
  is_prime_num(n)
  print(sum(arr[n+1:2*n+1]))
  n = int(input())

 

4. 9020번 골드바흐의 추측

처음에는 여러 개의 소수들 중 2개를 더해서 입력받은 짝수가 되는지를 검사하려고 했으나 이 방법으로는 시간 초과를 회피할 수 없었다. 그래서 생각한 방법으로 일단 소수를 하나 정하고 입력받은 짝수에서 그 소수를 뺏을 때 나온 값이 소수인지를 확인하는 방법으로 해결했다. 이 방법을 생각하기까지 시간이 좀 걸렸다.

#9020번 골드바흐의 추측
n = 10000
primes = []
#def prime(n) :
arr = [False,False] + [True]*(n+1)
for i in range(2,n+1):
  if arr[i]:
   primes.append(i)
  for j in range(2*i, n+1, i):
     arr[j] = False

def goldbach(num) : 
  x = num//2
  for i in range(x,num) : 
    if i in primes and num-i in primes : 
      return num-i,i
  
n = int(input())
for i in range(n) :
  even = int(input())
  a,b = goldbach(even)
  print("{} {}".format(a,b))

 

5. 1085번 직사각형에서 탈출

직사각형의 한쪽 점이 (0,0)이기 때문에 x, y, w-x, h-y 중 최솟값을 출력하면 된다.

#1085번 직사각형에서 탈출
x,y,w,h = input().split()
x = int(x)
y = int(y)
w = int(w)
h = int(h)

print(min(abs(x-w),x,y,abs(y-h)))

 

6. 3009번 네 번째 점

축에 평행한 직사각형이기 때문에 네 개의 점은 항상 다음과 같다.

(a, c)  (a, d)  (b, c)  (b, d)

위 사실을 알고 있고 세 개의 점이 주어진다면 네 번째 점을 구하는 것은 어렵지 않다.

#3009번 네 번째 점
x1,y1 = input().split()
x2,y2 = input().split()
x3,y3 = input().split()

x1 = int(x1)
y1 = int(y1)

x2 = int(x2)
y2 = int(y2)

x3 = int(x3)
y3 = int(y3)

x4 = 0
y4 = 0

if x1 == x2  :
  x4 = x3
elif x1 == x3 : 
  x4 = x2
else : x4 = x1

if y1 == y2  :
  y4 = y3
elif y1 == y3 : 
  y4 = y2
else : y4 = y1

print("{} {}".format(x4,y4))

 

7. 4153번 직각삼각형

피타고라스의 정리를 알고 있으면 쉽게 풀 수 있다. 파이썬에서 제곱, 루트는 **로 아주 쉽게 할 수 있다.

#4153번 직각삼각형

while True : 
  x,y,z = input().split()
  x = int(x)
  y = int(y)
  z = int(z)
  
  if x == 0 and y == 0 and z == 0 : break

  l = sorted([x,y,z])
  if l[0]**2 + l[1]**2 == l[2]**2 : print("right")
  else : print("wrong")

8. 3053번 택시 기하학

처음에 택시 기하학을 봤을 때는 "이게 뭐지?" 싶었다. 택시 기하학에서 두 점 T1(x1, y1), T2(x2, y2) 사이의 거리는 다음과 같다.

D(T1, T2) = |x1-x2| + |y1-y2|

한 점을 (0,0)으로 두면 기울기가 +-1인 네 개의 직선이 나오는데 원의 정의대로 점들을 모으면 정사각형이 나온다. 피타고라스의 정리를 통해 정사각형의 한 변의 길이를 구하고 이를 통해 정사각형의 넓이를 구할 수 있다.

#3053번 택시 기하학
import math
r = float(input())
print("%.6f"%(math.pi*r*r))
print("%.6f"%(2*(r**2)))

 

9. 1002번 터렛

두 원이 만나거나 만나지 않는 모든 경우를 체크해줘야 해서 하나라도 놓치면 틀리는 문제이다. 각 경우를 확인하고 구분하는 과정에서 조금 오래 걸렸다. 두 원은 크게 두 가지 경우가 존재한다. 두 원의 원점이 같은 경우와 다른 경우이다. 원점이 같은 경우일 때 반지름이 같으면 만나는 점이 무한이다. 반지름이 다르면 만나는 점은 존재하지 않는다. 두 원의 원점이 다를 때에는 다섯 가지 경우가 있다. 한원이 다른 원 안에 있고 만나지 않는 경우, 한원이 다른원 안에 있고 한 점에서 만나는 경우, 두 원이 겹치게 있는 경우, 한원이 다른원 바깥에 있고 한 점에서 만나는 경우, 두 원이 아예 멀리 떨어져 만나지 않는 경우이다. 각 경우들을 if문을 통해 정확히 나눠줘야 문제를 해결할 수 있다.

#1002번 터렛
n = int(input())

for i in range(n) : 
  x1,y1,r1,x2,y2,r2 = input().split()
  x1 = int(x1)
  y1 = int(y1)
  r1 = int(r1)

  x2 = int(x2)
  y2 = int(y2)
  r2 = int(r2)

  l = ((abs(x1-x2))**2 + (abs(y1-y2))**2)
  r = (r1+r2)**2
  r0 = (r1-r2)**2

  if l == 0 :
    if r1==r2: 
      print(-1) 
    else : 
     print(0)
  else : 
    if l == r or l == r0: 
      print(1)
    elif l > r or l < r0: 
      print(0)
    else : 
      print(2)