[Python] 백준알고리즘 #1934

r1verfuture·2021년 12월 24일

algorithm developer programming 코딩 파이썬 프로그래밍

백준알고리즘

목록 보기

68/110

📝 문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.
두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

⌨️ 입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

🖨 출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

⌨️ 예제 입력

🖨 예제 출력

45000
30
221

📚 내가 제출한 코드 1

t = int(input())
for _ in range(t):
  a, b = map(int, input().split())
  minValue = min(a, b); maxValue = max(a, b); gcf = 0
  for n in range(minValue, 1, -1):
    if minValue % n == 0 and maxValue % n == 0:
      gcf = n
      break
  if gcf == 0:
    print(a * b)
  else:
    print(a * b // gcf)

✏️ 내가 제출한 코드 1 에 대한 설명

input() : 키보드로 입력한 값을 받는 함수
a.split() : a를 빈칸 단위로 쪼개서 반환하는 함수
map(a, b) : b의 원소 하나하나를 a에 대입한 것을 반환하는 함수
min(a) : a들 중에서 가장 작은 값
max(a) : a들 중에서 가장 큰 값
range(a, b, c) : a부터 b 되기 전까지 c씩 더한 값들을 반환하는 함수 (ex. range(5, -1, -1) = 5, 4, 3, 2, 1, 0)
메모리 : 29200 KB
시간 : 4860 ms
코드 길이 : 298 B

📚 내가 제출한 코드 2

t = int(input())
for _ in range(t):
  a, b = map(int, input().split())
  q = 0; r = -1; tempA = a; tempB = b; result = 0
  while r != 0:
    q = tempA // tempB; r = tempA % tempB
    result = a * b // tempB
    tempA, tempB = tempB, r
  print(result)

✏️ 내가 제출한 코드 2 에 대한 설명

input() : 키보드로 입력한 값을 받는 함수
range(a) : 0부터 a-1까지의 정수를 반환하는 함수
a.split() : a를 빈칸 단위로 쪼개서 반환하는 함수
map(a, b) : b의 원소 하나하나를 a에 대입한 것을 반환하는 함수
메모리 : 29200 KB
시간 : 160 ms
코드 길이 : 250 B

🖇 내가 제출한 코드들 간의 비교

코드 1 을 쓸 때는 '유클리드 호제법' 이라는 방법에 대하여 알지 못한 상태였는데 시간이 너무 오래 걸려서 검색해보니 '유클리드 호제법' 을 사용하면 시간이 훨씬 단축된다는 사실을 알게 되었고, '유클리드 호제법' 이 무엇인지 검색해본 후 검색된 결과를 코드로 짜보니 실제로 시간이 훨씬 단축되었다.
코드 1 ('유클리드 호제법' 사용하지 않은 코드) 에서는 for 문으로 공약수를 모두 구해주는 방법을 사용했기 때문에 쓸데없는 실행 시간이 있었지만, 코드 2 ('유클리드 호제법' 사용한 코드) 에서는 쓸데없는 for 문 실행을 없애고 나눠주어야 하는 것만 빠르게 실행되었다. (숫자가 작은 경우에는 코드 1 도 괜찮을 수 있지만 숫자가 커지면 불필요한 for 문도 어쩔 수 없이 실행된다.)