[프로그래머스] 최대공약수와 최소공배수 구하기 / 유클리드 호제법

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

프로그래머스

---

---

문제 푼 코드

 

a > b 조건을 충족시켜주기 위해서 Math.max로 a에 큰 값을 Math.min으로 b에는 작은 값을 선언

a를 b로 나눈 나머지를 r

a = b, b = r 이 되어지며 b가 0이 될 때의 a가 최대 공약수가 되어짐

 

최대 공약수를 구한 것으로 최소공배수를 구한다.

최소공배수 = a * b / 최대공약수

---

본인은 수학을 매우 못한다...

해당 문제를 풀기위해서 중1 수학을 조금 살펴보았다.

소수, 공약수, 공배수, 소인수분해를 살펴보고 최대공약수와 최소공배수를 검색해보니 유클리드 호제법이라는게 있었다. 소인수분해를 해서 직접 찾으려는 것이 아니라 유클리드 호제법이라는 알고리즘을 사용하는 것이 더 빠르다고 한다.

 

- 유클리드 호제법이란?

A를 B로 나눈 몫을 Q라고 하고, 나머지를 R이라 한다면 이때, gcd(A, B) = gcd(B, R)이다.

간단한 예로 60를 24로 나눈 몫은 2이고 나머지는 12이다.

 

즉, 60=24×2+1260=24×2+12 이므로 gcd(60,24)=gcd(24,12)=12gcd(60,24)=gcd(24,12)=12임을 확인할 수 있다.

위 정리를 이용한 유클리드 호제법 알고리즘은 다음과 같다.

 

1. A와 B의 최대공약수를 구하기 위해서 A를 B로 나눈 나머지 R1을 구한다.
2. B를 R1으로 나눈 나머지 R2를 구한다.
3. R1을 R2로 나눈 나머지 R3를 구한다.
4. 이 과정을 계속 반복하여, 어느 한 쪽이 나누어떨어질 때까지 반복하며, 이 직전 얻은 나머지가 최대공약수이다.

조금 더 쉽게 쓰자면

 

최대 공약수를 유클리드 호제법을 이용해서 구한다면

임의의 두 자연수 a, b(a>b)가 주어지고 a를 b로 나눈 나머지를 r(r = a % b)라고 하면

a = b가되고 b = r이 되는데, 이때 b가 0이 될 때의 a가 최대공약수이다.

 

최소 공배수는 최소 공배수 * 최대 공약수 = a * b 임을 이용하여

최소 공배수 = a * b / 최대 공약수

---

공부할 때 참고한 사이트

https://dimenchoi.tistory.com/46

정수론 (1) - 최대공약수, 최소공배수, 유클리드 호제법

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

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