초보몽키의 개발공부로그

level 1. 최대공약수와 최소공배수 - gcd

08 Mar 2017 | 알고리즘 프로그래밍

level 1. 최대공약수와 최소공배수 - gcd

출처

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환해주는 gcdlcm 함수를 완성해 보세요. 배열의 맨 앞에 최대공약수, 그 다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 gcdlcm(3,12) 가 입력되면, [3, 12]를 반환해주면 됩니다.

풀이 (python)

1

from fractions import gcd
def gcdlcm(a, b):
    return [gcd(a,b), a*b/gcd(a,b)]


# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(gcdlcm(3,12))

2 (참고)

def gcdlcm(a, b):
    big, small = max(a, b), min(a, b)
    while small > 0:
        big, small = small, big % small
    return [big, int((a*b)/big)]

다른사람 풀이

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))

배운점

  • from fractions import gcd 모듈을 통해 최대공약수(Greatest Common Divisor) 를 구하는 함수 gcd()를 사용할 수 있다.
  • a,b의 최소공배수는 a*b/최대공약수 를 통해서 구할 수 있다.

Related Posts