코테 연습>최대공약수 최소공백수

문제 링크 : https://www.acmicpc.net/problem/2609

처음에 유클리드 호제법을 적용하지 않고 구현을 해보았다.

초기에 짠 코드:

a=24
b=18

unit_max =[]
unit_min = []

for i in range(min(a,b),0,-1):
  if a%i and b%i == 0:
    unit_max.append(i)
    break

for j in range(max(a,b),(a*b)+1):
  if i%a and i%b == 0:
    unit_min.append(j)
    break

      

print(unit_max)
print(unit_min)

출력해보니 18,24 나옴

import sys
input = sys.stdin.readline
 
a, b = map(int, input().split())

for i in range(b, 0, -1):
    if a % i == 0 and b % i == 0:
        print(i)
        print(i * a // i * b // i)
        exit()

구글링해서.. 찾은 코드.....

그리고 찾다보니 유클리드 호제법..? 이라는 것이 나온다.
이게 코딩테스트 공부하는건지.. 수학 공부를 하는 건지..

유클리드 호제법은 2개의 자연수 또는 정수의 최대공약수를 구하는 알고리즘의 하나로, 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정수) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수(gcd)는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
-> 구현한 코드

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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
    
print(gcd(a, b), a*b//gcd(a, b))