두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
if문으로 공통 약수를 구한 후 GCD 변수에 저장 -> 반복문에서 처음으로 조건문에 해당하는 값이 저장됨
해당 값을 result 리스트로 저장
최소 공배수
위의 내용 처럼 3과 12의 최소공배수를 구할 때 공통 배수가 12부터 시작하는 것을 알 수 있음
따라서, n,m값중 큰 값부터 시작하여 두 개를 곱한 값으로 범위를 지정
해당 조건문을 만족하는 i값이 나오면 LCM 변수에 저장하여 result 리스트에 추가함
불필요한 반복을 실행시키지 않도록 조건이 만족하면 break를 써서 반복문을 탈
def solution(n, m):
answer = 0
result = []
# 최대공약수
for i in range(min(n,m), 0, -1):
if (n % i) == 0 and (m % i == 0):
GCD = i
result.append(GCD)
break
# 최소공배수
for i in range(max(n,m), (n*m)+1):
if (i % n == 0) and (i % m == 0):
LCM = i
result.append(LCM)
break
return result
👉다른사람 풀이(유클리드호제)
유클리드 호제법은 큰 수를 작은 수로 나누어 나머지를 구하고, 작은 수를 나머지로 나누어 나머지가 0이 될 때까지 반복하여 최대공약수를 구하는 알고리즘
최대공약수를 구한 뒤, 이를 이용하여 최소공배수를 계산할 수 있음
최소공배수는 주어진 두 수의 곱을 최대공약수로 나눈 값
https://codingpractices.tistory.com/34 참고
def gcdlcm(a, b):
c,d = max(a, b), min(a, b)
t = 1
while t>0:
t = c%d
c, d = d, t
answer = [ c, int (a*b/c)]
return answer
# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(gcdlcm(3,12))
👉다른사람 풀이(lambda 함수 사용)
def solution(n, m):
gcd = lambda a,b : b if not a%b else gcd(b, a%b)
lcm = lambda a,b : a*b//gcd(a,b)
return [gcd(n, m), lcm(n, m)]
