[CodeUp] 최소공배수, 최대공약수 구하기

 

최대공약수와 최소공배수 구하는 문제에 대해서 다뤄보고자한다. 시작하기전에 유클리드 호제법에 대해서 먼저 아는 것이 중요하다. 

 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

---

<1071과 1029의 최대공약수 구하기>

 

1071 % 1029 = 42

1029 % 42 = 21

42 % 21 = 0

💡 최대공약수 = 21

 

1) 최대공약수를 구하고 싶은 두 수를 나누어 나머지를 구한다.

2) 나눌 때, 뒤에 있던 숫자를 앞으로 위치를 변경하고 나누어진 나머지와 다시 나누어 나머지를 구한다.

3) 계속해서 반복하다 0으로 나누어 떨어지는 수가 최대공약수이다. 

---

1️⃣ 최대공약수 구하기

위의 예시를 이용하여, 파이썬으로 최대공약수를 구현할 수 있다.

# 최대공약수 함수
def gcd(x,y):
	while y:
    	x, y = y, x%y # 위치를 변경하여 나머지가 0이 될 때까지, 반복
    return x

 

2️⃣ 최소공배수 구하기

최대공약수를 구했다면, 최대공약수를 이용하여 최소공배수도 구할 수 있다. 최대공약수는 두 숫자의 공통되는 가장 큰 약수로 두 수의 곱에서 큰 약수를 나누면, 가장 작은 공배수인 최소공배수를 구할 수 있다.

# 최소공배수 함수
def lcm(x,y)
	return x * y // gcd(x,y) # 두 수를 곱한 값과 최대공약수의 몫이 최소공배수

 

3️⃣ 2개의 수가 아닌 N개의 수에서 구하기

여태까지 함수는 2개의 숫자를 비교했다. 2개 이상의 숫자도 위의 식을 이용해서 구할 수 있다. 3개의 숫자라고 한다면, 첫번째와 두번째 숫자를 비교하고 나온 값과 세번째 숫자를 비교하면 3개의 숫자의 값을 구할 수 있다. 이런식으로 N개의 숫자들을 리스트안에서 비교하면서 진행하면 된다.

# 최대공약수 함수
def gcd(x,y):
    while y:
        x, y = y, x%y
    return x

# 최소공배수 함수
def lcm(x,y):
    return x * y // gcd(x,y)

## 3, 7, 9의 최대공약수 구하기
gcd_3_7 = gcd(3,7) # 두 수의 최대공약수
gcd_3_7_9 = gcd(gcd_3_7, 9) # 먼저 비교한 최대공약수와 남은 수를 비교하기

## 3, 7, 9의 최소공배수 구하기
lcm_3_7 = lcm(3,7)
lcm_3_7_9 = lcm(lcm_3_7, 9)

print(gcd_3_7_9) # 최소공약수 1
print(lcm_3_7_9) # 최소공배수 63

 

 

참고 문제 : https://codeup.kr/problem.php?id=6091