유클리드 호제법은 명시적으로 기술된 알고리즘 중에서 가장 오래된 알고리즘이라고 한다. 호제법이란 두 수가 서로 상대방의 수를 나누어서 원하는 수를 얻는 알고리즘을 의미한다. 유클리드 호제법을 이용하면 최대공약수를 쉽게 찾을 수 있다. 방법은 아래와 같다.
유클리드 호제법
1. A와 B중에서 큰 수를 작은 수로 나눈다. (A>B로 가정한다.)
2. 나머지가 0이라면 그 몫(Q)이 최대공약수가 된다.
3. 나머지가 0이 아니라면, 작은 수(B)를 나머지(R1)로 나눈다.
4. 나머지가 0이 아니라면, R1을 R2로 나눈다.
5. 나머지가 0이 될 때까지 반복한다. 0이 되면 그때의 나눈 수가 최대공약수이다.
결국 두 수는 두 수의 최대 공약수의 n배이기 때문에, 두 수를 계속 나누어서 가장 작은 단위(?)를 찾는 것이라고 이해하면 될 것 같다. 직접 숫자를 대입해서 풀어보자. a = 48, b = 18이라고 해보자.
48을 18로 나누면 나머지는 12이다. 나머지가 있으므로 작은 수인 18을 12로 나눈다. 이때도 나머지가 발생하므로 다시 12을 6으로 나눈다. 12 % 6은 나머지가 0이다. 이 때 6이 최대 공약수가 된다.
사실 글로 쓰면 처음에 이해가 쉽지 않은데, 위의 내용을 그림으로 보면 이해가 더 쉬워서 위키피디아에서 가져왔다.
위의 알고리즘을 자바스크립트에서 구현하면 다음과 같다. 여기서 재귀함수를 쓸 수 있다 .
function GCD(a, b) {
if (b === 0) {
return a;
} else {
return GCD(b, a % b);
}
}계속 나누면서 a와 b를 대체한다. a는 b로, b는 a % b를 한 나머지로. 만약 두 수가 서로소인 경우에는 최대공약수가 1로 출력된다.
기존에 학교에서 배웠던 방법처럼 두 수의 공통된 작은 수, 예를 들어 2부터 나누어 들어가기 시작하면 큰 수의 경우에는 나누는 과정이 엄청나게 많을 것이다. 유클리드 호제법을 사용하면 그 과정을 아주 효과적으로 단축할 수 있다. 따라서 미리 공부해두고 코딩테스트에 활용해보자!
