알고리즘
[프로그래머스] 최대공약수와 최소공배수
hminor
2023. 7. 4. 09:43
반응형
우선 유클리드 호제법은
- 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나.
그리고 호제법이란
- 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
# 유클리드 호제법으로 작성한 첫 코드
def gcd(n,m):
while m != False:
n,m = m, n%m
return n
def lcm(n,m,x):
return n*m//x
def solution(n, m):
x = gcd(n,m)
return [x,lcm(n,m,x)]
# 유클리드 호제법과 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)]