알고리즘 - 최대공약수 : 유클리드 호제법(Euclidean algorithm) GCD

유클리드 호제법 (BPEuclidean algorithm) GCD - 최대 공약수 구하기

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. - 위키백과

 

예시

2958, 1088 의 최대공약수를 구해보자 2958을 1088로 나눈다. 정확히 나누어지지 않기때문에 나머지를 구한다. 나머지 -> 782 1088을 782로 나눈다.  정확히 나누어지지 않기때문에 나머지를 구한다. 나머지 -> 306 782을 306로 나눈다.  정확히 나누어지지 않기때문에 나머지를 구한다. 나머지 -> 170 306을 170로 나눈다.  정확히 나누어지지 않기때문에 나머지를 구한다. 나머지 -> 136 170을 136로 나눈다.  정확히 나누어지지 않기때문에 나머지를 구한다. 나머지 -> 34 136을 34로 나눈다.  정확히 4로 나누어진다. 이로써 34가 2958, 1088 두 수의 최대공약수가 구해진다.

예시에서 확인한것과 같이 2958과 1088의 최대공약수를 6번의 연산만으로 구해졌다.

 

일반적으로 최대 공약수를 구하려 하였으면 두 수를 소인수 분해 한 후 공통된 소수를 찾아야 하는 번거로움이 있었겟지만 유클리드 호제법을 사용하면 간단하게 최대공약수를 구할 수 있다.

 

그렇다면 유클리드 호제법을 자바언어로 구현해보자

	// 최대공약수(유클리드 호제법)
	public int get_gcd(int a, int b) {
		int p = a;   //변수 p에 a값을 대입해준다.
		int q = b;   //변수 q에 a값을 대입해준다.
		int r= p % q; // r에는 p를 q로 나눈 나머지를 대입해준다.
		
		while(r != 0) { // r이 0이 아니라면 반록해준다.
			p = q;		// p에 q를 대입해준다.
			q = r;		// q에 r을 대입해준다.
			r = p % q;  // r에는 p를 q로 나눈 나머지를 대입해준다.
		}
		
		return q; // q를 리턴해준다. (최대공약수가 구해졌다.)
	}

get_gcd(int a, int b) 메소드가 유클리드 호제법을 사용한 최대공약수를 구하는 코드이다.

 

구름에듀에 있는 알고리즘 문제해결기법 입문 - 코딩몬스터 님의 강좌를 보고 유클리드 호제법에 대해 알게되었다.

(매일 강좌를보고 강좌에 커리큐럼에 맞도록 알고리즘, 자료구조, 코딩테스트에 대한 공부를 할 것이므로 알고리즘에 대한 포스팅이 순서가 맞지 않더라도 이해 부탁드립니다.)

알고리즘 문제해결기법 입문 - 구름EDU

공부하여 백준에서 유클리드 호제법을 이용하여 문제를 풀어보자

문제보기

www.acmicpc.net/problem/1850