[유클리드 호제법 알고리즘] 최대공약수, 최소공배수 구하기

유클리드 호제법

1. 최대공약수

최대공약수를 구하는 가장 쉬운 알고리즘, 유클리드 호제법

 

두 수 A와 B가 주어졌다고 생각해보자. (A>B)

A와 B의 최대 공약수는 n이라고 하자.

그러면 A=n*?, B=n*?? 이런 구조일 것이다.

결국 A-B, B-(A-B), (A-B)-(B-(A-B)) ,,,,,,,, 이런 식으로 계속 빼다보면 언젠가 최소 단위인 n이 나올 것이다.

이 그림을 보면 이해가 될 것이다.

A에서 B를 빼고, 다시 B에서 그 A-B를 빼고 이런 과정을 반복하다 보면 언젠가 n이 나오고 맨 마지막엔 0이 나올 것이다.

둘 다 n이 남았으니 말이다.

 

반응형

 

 

여기서 아이디어를 추가해보자.

계속 빼는 것도 좋지만, A와 B의 차이가 크면 너무 무의미한 계산의 반복이다.

결국 A%B, A를 B로 나눈 나머지 값이 결국 여러 번 뺀 값이 되는 것이다.

 

예시를 들어보자.

1112와 695의 최대공약수를 구해보자.

(1112, 695) 나눈 나머지는 417이다.

다시 695를 417로 나눈 나머지는 278이다

다시 417을 278로 나눈 나머지는 139이다.

마지막으로 278을 139로 나눈 나머지는 0이다.

결국, 139가 둘의 최대공약수인 것이다.

 

728x90

 

이제 이걸 코드로 나타내보자.

// GCD: Greatest Common Divisor
public static int GCD(int A, int B){
	if(B==0){return A;}
    return GCD(B, A%B);
}

 

 

어짜피 계속된 반복이기 때문에 재귀함수를 만들어주면 된다.

하지만 B==0이 되는 순간에 A값을 return해주면 된다.

 

public static int GCD(int A, int B){
	return B==0 ? A : GCD(B,A%B);
}

참고로 ? 와 : 를 이용해서 if else 구조를 대신할 수도 있다.

혹시나 if else 구조를 ? : 로 바꾸는게 궁금하다면 간단하게 설명을 봐도 된다.

https://moonsonghada.tistory.com/34

[JAVA] 물음표(?)와 콜론(:)으로 if else 문 간단하게 만들기

 

 

 

2. 최소공배수

최소공배수는 최대공약수를 알면 끝난다.

A=n*a이고 B=n*b이기 때문에 최소공배수는 n*b*a이다.

// LCM : Least Common Multiple
public static int LCM(int A, int B){
	return A*B/GCD(A,B);
}

따라서 그냥 A*B하고 GCD(A,B)를 나눠주면 끝이다.