유클리드 호제법 이란 무엇인가?

▏목적

 

      ◦ 유클리드 호제법 알고리즘 이해하기

      ◦ 유클리드 호제법 JAVA로 구현하기

 

 

 

 

▏시작하는 말

 

요즘 팀 프로젝트 작업을 하고 있어 알고리즘 공부하는 것이 뜸했다. 그래서 오늘은 일찍부터 일어나 공부를 시작해봤다. 오늘 공부한 것은 유클리드 호제법이란 알고리즘으로 최대공약수를 재귀적으로 구하는 방법이다. 예전에 내가 최대공약수 문제를 풀 때 정사각형으로 만드는 방법을 얼핏 봤었는데 그것을 오늘 제대로 공부했고 이제 설명해보려고 한다. 오늘도 역시 직접 그림판으로 그린 것이라 비율이 정확히 맞지는 않는것을 유념하고 봐줬으면 좋겠다.

 

 

 

▏유클리드 호제법

 

각 변의 길이가 22 와 8인 직사각형으로 예를 들어 설명해보겠다.

 

 

 

위 도형에서 짧은 변(8)을 한 변으로 하는 정사각형으로 나누면 8 x 8 정사각형 2개와 6 x 8 정사각형 1개가 나온다.

 

이 과정을 n번 수행하면 아래 그림과 같이 마지막으로 2 x 2 정사각형 3개가 나오며 직사각형은 더이상 생기지 않게 된다.

 

이 때 2가 최대공약수가 되는것이다.

 

 

 

두 정수가 주어질 때 큰 값을 작은 값으로 나누고, 나머지가 생길 경우 그 값에 대해 나누어 떨어질 때 까지 재귀적으로 n번 반복한다. 이 과정을 거쳤을 때 나누어 떨어지는 가장 작은 값이 최대공약수가 되는것이다.

 

수식으로 설명해보자면, 

 

x, y 의 최대공약수는 x = ai, y=bi를 만족하는 최대의 정수 i가 존재할 때 i 를 최대공약수 gcd(x,y)라 한다. 즉, y == 0 이면 x, 아니면 gcd(y, x % y)로 구하면 되는것이다.

 

public static int gcd(int x, int y) {

	if(y==0) {
		return x;
	}else {
		return gcd(y, x % y);
	}		
}

 

 

 

이번엔는 응용해서 배열로 주어질 때, 최대공약수를 구해보겠다.

 

배열개수를 하나씩 줄이면서 재귀적으로 함수를 호출하여 2개씩 gcd 작업을 거치고 그 값과 다음에 올 값을 계속해서 비교해나가면 된다.

 

public static int gcdArr(int[] arr, int start, int size) {

	if(size == 1) {
		return arr[start];
	}else if(size == 2){
		return gcd(arr[start], arr[start+1]);
	}else {
		return gcd(arr[start], gcdArr(arr, start+1, size-1));
	}
}

 

 

 

 

▏참고 자료

 

https://haams704.tistory.com/53