백준 2609 최대공약수와 최소공배수 Java
2019. 4. 15.
최대공약수를 구하기 위한 유클리드 호제법을 처음 알게 되었다. 알고리즘이 간단하여 금방 외울 수 있었다. 어떤 수 a와 b의 최대공약수는 b, a%b의 최대공약수와 같다는 성질을 이용한 알고리즘 이다. 재귀호출로 구현하는 방법과 반복문으로 구현하는 방법이 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 static int gcd1(int a, int b) { //재귀 사용 if(b==0) return a; return gcd1(b, a%b); } static int gcd2(int a, int b) { //반복문 사용 while(b!=0) { int r = a%b; a=b; b=r; } return a; } 또한 최소공배수를 구할 때도 최대공약수를 이용해 구할 수 있다. 최소공배수 lc..
