최대공약수 & 최소공배수.md

[알고리즘] 최대공약수 & 최소공배수

---

면접 손코딩으로 출제가 많이 되는 유형 - 초등학교 때 배운 최대공약수와 최소공배수를 구현하기

최대 공약수는 유클리드 공식을 통해 쉽게 도출해낼 수 있다.

ex) 24와 18의 최대공약수는?

유클리드 호제법을 활용하자!

주어진 값에서 큰 값 % 작은 값으로 나머지를 구한다.

나머지가 0이 아니면, 작은 값 % 나머지 값을 재귀함수로 계속 진행

나머지가 0이 되면, 그때의 작은 값이 '최대공약수'이다.

최소 공배수는 간단하다. 주어진 값들끼리 곱한 값을 '최대공약수'로 나누면 끝!

public static void main(String[] args) {
	int a = 24; int b = 18;
	int res = gcd(a,b);
	System.out.println("최대공약수 : " + res);
	System.out.println("최소공배수 : " + (a*b)/res); // a*b를 최대공약수로 나눈다
}

public static int gcd(int a, int b) { // 최대공약수
	
	if(a < b) swap(a,b)// b가 더 크면 swap
	
	int num = a%b;
	if(num == 0) return b;
	
	return gcd(b, num);
}