수학은 나에게 참 어려운 과목이다.
그래도 최대공약수, 최소공배수 이쯤이야~~ 풀수 있다.
하지만.. 이걸 코딩으로?.....
구현을 하자니... 내가 풀어온 공식들이 머릿속에서 엉퀴기 시작해 손이 5분간 멈춰있던 것 같다.
검색하는 도중 유클리드 알고리즘 (유클리드 호제법)을 알게되었다.
== 유클리드 알고리즘(유클리드 호제법) ==
자연수의 최대공약수를 구하는 알고리즘의 하나이다.
a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a ＞ b / r은 0 ≤ r＜ b)
a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
b를 r로 나눈 나머지 r`를 구하고 다시 r을 r`로 나눈 나머지를 구하는 과정을 반복하여
나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.// 최대공약수를 재귀함수로 구현하시오.
// 유클리드 알고리즘 (유클리드 호제법)
// a, b : 정수, r : 나머지
// gcd(a, b) = gcd(b, r) = gcd(b, a % b)
public class Practice2 {
static int gcd(int a, int b){
// 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수
if(a % b == 0){
return b;
}
return gcd(b, a % b);
}
public static void main(String[] args){
// Test Code
System.out.println(gcd(3, 5));
System.out.println(gcd(2, 6));
System.out.println(gcd(8, 12));
}
}
수학을.. 코딩으로 구현하기란... 나에겐 힘든 것 같다.
그럼에도 불구하고...
재밌다~!!
