[백준/튼튼한기본기] 2609번: 최대공약수와 최대공배수

[문제]

 

[내 코드]

- 버전1: 주어진 숫자마다 약수 리스트를 만들었다

- 76ms 걸렸다

- 리스트 만드는 습관을 버리고자.. 다른 방법을 모색해봄

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

a_list = [i for i in range(1, a+1) if a%i == 0]
b_list = [j for j in range(1, b+1) if b%j == 0]

r1 = max(list(set(a_list)&set(b_list)))
print(r1)

r2 = r1 * (a//r1) * (b//r1)
print(r2)

 

- 버전2: 주어진 숫자 중에서 작은 수를 기준으로 높은 수부터 약수를 구했다 (ex. 24면 24, 23, 22, 21, .. 로 for loop에서 나눔)

- 살짝 줄어들어 72ms

[a, b] = sorted(list(map(int, input().split())))

for i in range(a, 0, -1):
    if (a%i==0) & (b%i==0):
        r1 = i
        break

print(r1)
r2 = r1 * (a//r1) * (b//r1)
print(r2)

 

[개선안]

일단 math 모듈을 사용하는 방법이 있다

import math
a, b = map(int, input().split())
print(math.gcd(a,b))
print(math.lcm(a,b))

 

유클리드 호제법을 사용하는 방법이 있다

두 자연수 a, b(a>b)가 있을 때, a를 b로 나눈 나머지를 r이라고 하자

a, b의 최대공약수와 b, r의 최대공약수가 같고(GCD(a, b) = GCD(b, r)), r이 0일 때 b가 최대공약수가 된다

 

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a

큰 수 a 와 작은 수 b 가 있을 때,

작은 수 b 가 0이 될 때까지 (나머지가 0이 되어 나누어 떨어질 때까지):

큰 수를 작은 수로 바꾸고 작은 수를 (큰 수를 작은 수로 나눈 나머지)로 교체한다

작은 수가 0이 될 때 큰 수가 최대공약수다

 

def lcm(a, b):
    return (a * b) // gcd(a, b)

 

최대 공배수는 두 값을 곱한 다음 최대공약수로 나누면 된다