[백준] 2609 최대공약수와 최소공배수 (Python)

2024. 7. 5. 13:29·Algorithm 뽀개기

이런! 최소공배수가 뭔지 기억이 안 날 뻔 했다. 심각한 수학 실력... 수학 포기하지 말걸~~~,,, 컴퓨터 공학과를 꿈꾸는 청소년 여러분 수학 포기하지 마세요 제발... 최대 공약수는 유클리드 호제법으로 구할 수 있다. 유클리드 호제법은 나누고 나눈 수를 나머지로 나누는 알고리즘이다.

유클리드 호제법

먼저 큰 수를 작은 수로 나눈 나머지를 구한다. 그 다음 나눴던 수를 나머지로 또 나누어 나머지를 구한다. 나머지가 0 이 되었을 때 마지막 계산에서 나누는 수로 사용된 숫자가 두 수의 최대공약수가 된다.

 

이를 반복문과 재귀함수로 구현할 수 있다. 

# 반복문
def gcd(a,b) :
    while b != 0 :
        a, b = b, a % b
    return a
# 재귀 함수
 def gcd (a,b) :
     if b == 0 :
         return a
     return gcd(b, a % b)
n, m = map(int, input().split())

def gcd(a,b) :
    while b != 0 :
        a, b = b, a % b
    return a
    
def lcm(a,b) :
    return a * b // gcd(a,b)
    
print(gcd(n,m))
print(lcm(n,m))

 

'Algorithm 뽀개기' 카테고리의 다른 글

Dynamic Programming, DP  (1) 2024.07.23
[백준] 6588 골드바흐의 추측 - 에라토스테네스의 체 (Python)  (1) 2024.07.21
[백준] 11655 ROT13 (Python) 출력 형식이 잘못되었습니다  (0) 2024.07.04
[백준] 10820 문자열 분석 (Python)  (1) 2024.07.03
[백준] 17298 오큰수 (Python)  (0) 2024.07.01
'Algorithm 뽀개기' 카테고리의 다른 글
  • Dynamic Programming, DP
  • [백준] 6588 골드바흐의 추측 - 에라토스테네스의 체 (Python)
  • [백준] 11655 ROT13 (Python) 출력 형식이 잘못되었습니다
  • [백준] 10820 문자열 분석 (Python)
daun_up
daun_up
가나디 발을 씻자
빌려온 가나디가나디 발을 씻자
daun_up
빌려온 가나디
daun_up
전체
오늘
어제
글쓰기 관리
  • 분류 전체보기 (37)
    • Algorithm 뽀개기 (19)
    • React.js 마스터 하기 (1)
    • 봄봄 Spring 이 왔어요 (3)
    • Nuxt.js 아는 척 하기 (2)
    • JavaScript 정복하기 (3)
    • 또error났니 (0)
    • 주제 업슴 (6)
    • Nomadcoders 보는 중이 싫으면 절이 떠나.. (2)
hELLO· Designed By정상우.v4.6.1
daun_up
[백준] 2609 최대공약수와 최소공배수 (Python)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.