자바 유클리드 호제법으로 최대공약수 구하기

오늘 수업 때 나온 연습문제 중에서 최대공약수를 구해야 풀 수 있는 문제가 있었다.

 

최대공약수 자체는 중학생 수준의 문제였는데, 최대공약수를 구하는 로직이 신기해서 기록해두려고 한다.

 

유클리드 호제법에 대한 설명은 위키백과에서 긁어 오겠다.

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

---

문제

두 수를 입력받아 최대공약수를 구한다.

입력

인자 1: num1

int 타입의 정수

인자 2: num2

int 타입의 정수

출력

int 타입의 정수

입출력 예시

int output = gcd(4, 8);
system.out.println(output);	// --> 4

---

이번 문제는 내가 풀었다고 할만한 것도 없으니, 코드의 흐름을 보면서 기록하겠다.

public class GreatCommonDivisionExample {
	public int gcd(int num1, int num2){	// num1 -> 4, num2 -> 8
    	if(num1 % num2 == 0) return num2;	// 4 % 8 == 4
        return gcd(num2, num1 % num2);		// gcd(8, 4)
    }
}

입출력 예시대로 num1에 4, num2에 8이 할당되면 if문은 참이 아니므로 if문 아래에 있는 리턴문이 실행되고 재귀 호출을 하게 된다.

이때 재귀호출에서의 인자의 값은 큰 값이 num1에 할당되고 작은 값이 num2에 할당되게 바뀐다. 대단하다.

 

public class GreatCommonDivisionExample {
	public int gcd(int num1, int num2){	// num1 -> 8, num2 -> 4
    	if(num1 % num2 == 0) return num2;	// 8 % 4 == 0 --> return 4
        return gcd(num2, num1 % num2);		
    }
}

재귀 호출되었을 때 num1에 8, num2에는 4가 할당된다. 그러면 if문은 참이므로 num2의 값인 4가 반환된다.

 

그러면 입출력 예시처럼 

int output = gcd(4, 8);
system.out.println(output);	// --> 4

gcd(4, 8)의 값을 출력했을 때 4가 출력될 것이다.

---

이번 포스팅에서는 별거 없지만 신기해서 기록해봤는데 다음에는 좀 어려웠던 문제를 올려야겠다.

 

슨배임들 조언 환영합니다.