지굥
Long day's journey into
지굥

티스토리

  • 분류 전체보기 (46)
    • 개발 (44)
      • TIL (11)
      • JavaScript (0)
      • Python (2)
      • 알고리즘 (30)
      • Git (1)
    • 책 (1)
    • 일상 (1)

인기 글

최근 글

전체 방문자
오늘
어제
hELLO · Designed By 정상우.
지굥

Long day's journey into

개발/알고리즘

[알고리즘] 최대공약수, 최소공배수 - 파이썬

2021. 6. 24. 16:38

최대공약수 : a와 b의 최대공약수는 (a를 b로 나눈 나머지)와 b의 최대공약수와 같다.

큰 수를 작은 수로 나눈 나머지로 큰 수를 대체한다. 큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다. 나누어 떨어질 때(나머지가 0일 때), 나누는 수가 최대공약수이다.

 

def gcd(a,b):
    if b < a:
        a,b = b,a

    while b:
        n = a % b
        a, b = b, n
        
    return a

최소공배수 = 두 수의 곱 / 최대공약수

def lcm(a,b):
    return (a*b)//gcd(a,b)

https://wikidocs.net/21759

 

 

위키독스

온라인 책을 제작 공유하는 플랫폼 서비스

wikidocs.net

https://blockdmask.tistory.com/53

 

[유클리드 알고리즘] GCD 최대공약수 (반복문, 재귀)

안녕하세요. BlockDMask 입니다. 유클리드 알고리즘은 사실 알고리즘 카테고리를 새로 만들어서 작성해야하는데, 조만간에 이사하도록 하겠습니다. 1) "유클리드 알고리즘"이란. 유클리드 알고리

blockdmask.tistory.com

https://myjamong.tistory.com/138

 

최대공약수(GCD), 최소공배수(LCM) 구하기 유클리드 호제법 알고리즘 :: 코드자몽

최대공약수 GCD(Greatest Common Divisor) 최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다. ex) 72 와 30의 최대공약수는 6이다. 최소공배수 LCM(Least Common Multiple) 최소공배수는 두 자연..

myjamong.tistory.com

 

저작자표시 (새창열림)

'개발 > 알고리즘' 카테고리의 다른 글

[프로그래머스 12899]124 나라의 숫자 - 파이썬 풀이  (0) 2021.11.04
[BOJ 10814] 나이순 정렬 - 파이썬, 람다  (0) 2021.07.20
[알고리즘] 소수 판별하기 - 파이썬  (0) 2021.06.24
[자료구조] 스택, 큐 구현 - 파이썬 deque  (0) 2021.06.24
[BOJ(백준) 10250] ACM호텔 - 파이썬 풀이  (0) 2021.06.01
    '개발/알고리즘' 카테고리의 다른 글
    • [프로그래머스 12899]124 나라의 숫자 - 파이썬 풀이
    • [BOJ 10814] 나이순 정렬 - 파이썬, 람다
    • [알고리즘] 소수 판별하기 - 파이썬
    • [자료구조] 스택, 큐 구현 - 파이썬 deque
    지굥
    지굥
    프론트엔드 개발자가 되려고 공부하고 있습니다.

    티스토리툴바