최대 공약수 최소 공배수
최대 공약수, 최소 공배수는 코딩테스트 등에서 은근 많이 쓰이는 개념이다. 식을 외워두면 금방 구하기 떄문에 특히 최대공약수 공식은 외워 두는게 좋다. 최대공약수 (Greatest Common Divisor, GCD) 유클리드 호재법으로 구할 수 있다. 재귀를 이용하면 짧은 코드를 만들 수 있다. 나머지가 0이 될 때까지 두 수의 자리를 바꿔가면서 구하면 된다. // 최대공약수 재귀 함수. 한쪽이 0이 될 때까지 스왑하면서 나머지를 구한다. public int GCD(int a, int b) { if(b == 0) return a; else return GCD(b, a % b); } 최소공배수 (Least Common Multiple: LCM) 두 수를 곱한다음, 최대공약수로 나눠주기만 하면 되기 때문에..