[자바 Do It! 알고리즘]Chapter05 재귀 알고리즘 (유클리드 호제법)

알고리즘 책을 보면 볼수록, 세상에는 천재가 많다고 느껴집니다.

이런 천재들과 같은 세상에서 살고 있다는 것이 신기하기도 하며

한없이 작아집니다.

그럼에도 천재들의 시야를 빌릴 수 있어서 감사합니다.

​

[유클리드 호제법]

1. 두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법입니다.

두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제는 다음 문제처럼 바꿀 수 있습니다.

★ 직사각형을 정사각형으로 완전히 채웁니다. 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하세요.

(1) 22 X 8 크기의 직사각형에서 짧은 변(8)을 한 변으로 하는 정사각형으로 분할합니다.(a).

이렇게 하면 (b)처럼 8 X 8 크기의 정사각형 타일 2장이 생깁니다. 그리고 8 X 6 크기의 직사각형이 1개 남습니다.

(2) 남은 8 X 6 크기의 직사각형으로 다시 같은 과정을 수행합니다.(c). 6 X 6 크기의 정사각형이 1개, 6 X 2 크기의 직사각형이 1개 남습니다.

(3) 다시 남은 6 X 2 크기의 직사각형으로 같은 과정을 수행합니다.(d). 이번에는 2 x 2 크기의 정사각형 3개로 나눌 수 있습니다. 여기서 얻은 2가 최대공약수입니다.

​

이렇게 두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어떨어지는 가장 작은 값이 최대공약수입니다.(과정 3) 나누어지지 않으면 작은 값(얻은 나머지)에 대해 나누어떨어질때까지 같은 과정을 재귀적으로 반복합니다.(과정 1,2)

​

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

두 정수 x, y의 최대공약수를 gcd(x, y)로 표기하면, x=az와 y=bz를 만족하는 정수 a, b와 최대의 정수 z가 존재할 때 z를 gcd(x,y)라고 할 수 있습니다. 다시 말 해 최대공약수는 y가 0이면 x이고, y가 0이 아니면 gcd(y, x % )로 구합니다.

솔직히 무슨 말인지 잘 모르겠으나, x=3, y=6 일경우, x=6, y=3 일 경우로 대입하면 그때는 이해갑니다.

​