[문제] 최대공약수와 최소공배수

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 작성해보세요.

나의풀이

숫자가 커지는 만큼 더 많은 시행을 시도해야 할 확률이 높다.

O(n) 이라 할 수 있겠다.

def solution(n, m):
    answer = []
    
    # a가 b보다 크다
    
    if n>m:
        a=n
        b=m
    else:
        a=m
        b=n
    
    yaksu = 1
    
    # '최대'공약수니까 큰것부터
    for i in reversed(range(b+1)):
        if a%i==0 and b%i==0:
            yaksu = i
            break
            
    baesu = a
    i=1
    while True:
        if a*i % b ==0:
            baesu = a*i
            break
            
        i+=1
    
    answer = [yaksu, baesu]
    
    return answer

다른 사람의 풀이

유클리드 호제법을 사용하였다. (먼저 큰 수를 작은수로 나누고, 몫을 나머지로 나누는 시행을 반복해서 나머지가 0일 때의 몫을 최대공약수로 한다.)

O(1) 인가? 무튼 훨씬 작은, 비교적 정해진 횟수의 시행으로 답을 구할 수 있다.

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