[Algorithm]최대공약수 & 최소공배수 - Java

[알고리즘] 최대공약수 & 최소공배수 - Java 로 구현하기

많은 사람들이 코딩테스트 문제를 풀다보면 접하게 되는 최대공약수 & 최소공배수 구하기 이다. 

 

학생 시절에 배웠던것이라 기억이 나는 사람도 나지 않는 사람도 있을것이다. 

또한 알고 있더라도 코드로는 접근하기 어려울수 있기 때문에 한번은 공부해두면 좋을것 같다. 

 

최대 공약수를 코드로 구현하는 방법은 2가지가 있다! (변형해서 사용가능)

- 반복문 사용(for ,while)

- 재귀함수 사용

 

최소 공배수를 코드로 구현하는 방법은 두 수 a,b 가 존재할때 a,b의 최대 공약수를 구한후 

공식 : a * b / 최대공약수 

해당 공식으로 구할 수 있다. (본 글에서는 예제를 위해 메서드로 구현)

---

유클리드 호제법 

유클리드 호제법이란? 

2개 수의 최대 공약수를 구하는 방법(알고리즘) 이다. 

공식은 아래에 있는것이지만 쉽게 말로 풀어보자면

-> 자연수 a,b 에 대해서 -> a를 b로 나눈 나머지는 r 이라고 할때

-> a,b의 최대 공약수는, b,r의 최대 공약수와 같다. 이런것에 따라 

-> r을 구하고 b를 r로 나눈 후 나머지를 구한다. 

-> 나머지가 0이 되면 이때 나누었던 b가 최대 공약수가 된다!!!!

 

공식

두 양의 정수 a,b (a>b)a,b (a>b)에 대하여 a=bq+r (0≤r<b)a=bq+r(0≤r<b)이라 하면, a,ba,b의 최대공약수는 b,rb,r의 최대공약수와 같다. 즉, 

gcd⁡(a, b)=gcd⁡(b, r)gcd(a, b)=gcd(b, r)

r=0r=0이라면, a,ba,b의 최대공약수는 bb가 된다. 

---

개념 및 코드 

최대 공약수 : 두 수 이상의 여러 수의 공약수 중 최대인 수

     - GCD 라고 한다. (Greatest Common Divisor)

     - 구하는 방법은 반복문 사용, 재귀 함수 사용 2가지가 존재한다! 

     

1) 반복문(for)을 사용한 최대공약수 구하기

1-1 작은 수를 구하는 이유는 최대 공약수는 작은 수 보다 클 수가 없기 때문이다. 

       시작값 1부터 작은수의 값까지 반복하며 최대 공약수를 구한다. 

       - 두 수 a,b 가 i 로 나누어진다면 마지막으로 저장되는 i가 최대 공약수이다.

2) 재귀를 통한 최대공약수 구하기 

2-1 해당 방법은 '유클리드 호제법' 을 사용한 코드이다. 

      - a % b 의 나머지가 0일 경우!  숫자 b 를 return 하여 마무리한다. 

      - 나머지가 0이 될 때 까지 재귀 함수를 호출한다.

 

최소 공배수 : 두 수 이상의 여러 수의 공배수 중 최소인 수 

     - LCM 이라고 한다 (Lowest Common Multiple)

     - 두 숫자를 곱한 후 두 수의 최대공약수로 나누면 최소 공배수가 된다 !

---

해당 전체 코드는 아래 링크에서 확인하세요 !

https://github.com/swings134man/DataStructure_Java/blob/main/src/algorithm/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98_%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98.java

GitHub - swings134man/DataStructure_Java: 자료구조 & 알고리즘

 

틀린점이나 수정할 부분이 있으면 언제든 자유롭게 피드백 주세요~!