본문 바로가기
Algorithm/구현

[Python3] 백준 2609번 최대공약수와 최소공배수

by HANNI하니 2022. 1. 2.

try 2 times / 난이도 : ★ (난이도는 제가 느끼는 매우 주관적인 난이도입니다.)

문제 확인

2609번: 최대공약수와 최소공배수

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

www.acmicpc.net

코드 깃허브 확인

GitHub - yyeongeun/codingtest: 코딩테스트 공부

코딩테스트 공부. Contribute to yyeongeun/codingtest development by creating an account on GitHub.

github.com

정답 해설

유클리드 호제법을 사용하여 최대공약수와 최소공배수를 구한다.

a,b = map(int,input().split())

# 최대공약수
# a & b의 최대 공약수는 b & a를 b로 나눈 나머지의 최대 공약수
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

# 최소공배수 
# a와 b의 곱을 a와 b의 최대 공약수로 나눈 값
def lcm(a, b):
    return a * b // gcd(a, b)


print(gcd(a, b))
print(lcm(a, b))

공부한 내용

1. 유클리드 호제법

a & b의 최대 공약수는 b & a를 b로 나눈 나머지의 최대 공약수와 같다.
단, a > b여야 a를 b로 나눈 나머지를 구할 수 있다.
a, b
= b, a % b = b, r
= r, b % r = r, r'
= r', r % r' = r',r''
이 과정을 반복하여 나머지(r'')가 0이 되었을 때 나누는 수(r')이 a와 b의 최대공약수이다.
나누는 수(r')은 a로 저장되어 있으므로 a를 return한다.

최소공배수는 a와 b의 곱을 a와 b의 최대 공약수로 나눈 값

2. 다른 풀이 이해하기

내장 함수 사용하기
함수가 내장되어 있지만 코테 공부를 위해서 함수를 사용하는 것보다 직접 작성할 줄 알아야한다.

import math

a,b = map(int,input().split())

print(math.gcd(a,b))
print(math.lcm(a,b))


레퍼런스

  • 유클리드 호제법 설명

유클리드 호제법

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b), a와 b의 최대공약수는 b

velog.io

댓글