say repository

[프로그래머스] 최대공약수와 최소공배수 python 본문

알고리즘 문제 풀이/프로그래머스

[프로그래머스] 최대공약수와 최소공배수 python

부끄러엇피치 2022. 4. 4. 15:18
728x90

https://programmers.co.kr/learn/courses/30/lessons/12940

 

코딩테스트 연습 - 최대공약수와 최소공배수

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

programmers.co.kr

출처 : 프로그래머스

def gcd(a,b):
    if a<b:
        a,b = b,a
    while b!=0:
        a,b = b, a%b
    return a

def solution(n, m):
    answer = []
    answer.append(gcd(n,m))
    answer.append(n*m//gcd(n,m))
    return answer

풀이

유클리드 호제법 알고리즘이다.

최대공약수는 math.gcd(n,m) 으로 구할 수도 있다.

최소공배수는 n*m//gcd(n,m) -> 즉, 두 수의 곱에 두 수의 최대공약수를 곱한 값과 같다.

저작자표시 비영리 변경금지 (새창열림)

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 소수 찾기 python  (0) 2022.04.05
[프로그래머스] [1차] 비밀지도 python  (0) 2022.04.05
[프로그래머스] 시저 암호 python (*)  (0) 2022.04.02
[프로그래머스] 이상한 문자 만들기 python  (0) 2022.04.02
[프로그래머스] 행렬의 덧셈 python  (0) 2022.04.02
'알고리즘 문제 풀이/프로그래머스' Related Articles more