[JAVA] 유클리드 호제법 - 최소공약수 구하기

코딩테스트 문제를 풀다보면 최소공약수를 구해야하는 경우가 있다.

이 때, 사용하면 좋은 것이 유클리드 호제법이다.

유클리드 호제법을 자바코드로 표현하면 다음과 같다.

public static int gcd(int p, int q)
 {
	if (q == 0) return p;
	return gcd(q, p%q);
 }

계산을 한번 해보도록 하자.

예를 들어 p=7, q=20이라고 하면

 

(1) gcd(7, 20) 

-> q==0이 아니기 때문에 return gcd(20, 7%20) = gcd(20, 7)

 

(2) gcd(20, 7)

-> q==0이 아니고 20이기 때문에 return gcd(7, 20%7) = gcd(7, 6)

 

(3) gcd(7, 6)

-> q==0이 아니고 6이기 때문에 return gcd(6, 7%6) = gcd(6, 1)

 

(4) gcd(6, 1)

-> q==0이 아니고 1이기 때문에 return gcd(1, 6%1) = gcd(1, 1)

 

(5) gcd(1, 1)

-> q==0이 아니고 1이기 때문에 return gcd(1, 1%1) = gcd(1, 0)

 

(6) gcd(1, 0)

-> q==0 성립, 따라서 return 1;

 

1이 리턴되므로 7과 20의 최대공약수는 1임을 알 수 있다.

이제 이를 기억해두었다가 사용해서 코딩테스트에 사용하면 된다!