TIL 51일차_알고리즘: 유클리드 호제법

개인공부/TIL(Today I Learned)

soon327 2021. 3. 10. 01:31

호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다.
이 뜻의 '호제' 라는 단어가 따로 있지는 않다.
이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다.

유클리드 호제법 개념

알고리즘의 골자는 다음과 같다.

두 양의 정수 a, b (a>b)에 대하여
a = bq + r (0 <= r < b)라 하면,
a,b의 최대공약수는 b,r의 최대 공약수와 같다.
즉, gcd(a,b) = gcd(b,r) 이며
r=0이라면 a,b의 최대공약수는 b가 된다.

1112와 695를 유클리드 호제법에 대입해보면
a = b * q + r
1112 = 695 * 1 + 417 이다.

1112와 695의 최대공약수는
695와 417 ( = 1112 % 695 )의 최대공약수와 같고
417과 278 ( = 695 % 417 )의 최대공약수와 같고
278과 139 ( = 417 % 278)의 최대공약수와 같고....

139와 0 ( = 278 % 139 )
r = 0이 됐을 때,
즉 계속 서로를 나누다가 a가 b의 배수가 됐을 때의 b가 최대공약수가 된다.

위처럼 직접 계산할 때는 두 수의 대소를 비교해서 적절하게 배열해야 하지만,
수식이나 코드로 나타낼 때는 신경쓰지 않아도 된다.

왜냐??
코드를 보면,
a<b일 때 a%b === a이므로 gcd(a,b)는 gcd(b,a)를 호출한다.
즉 재귀 과정에서 자연스럽게 큰 값이 a로, 작은 값이 b로 들어간다.

// 최대공약수
function gcd(a,b)
return (a % b) === 0 ? b : gcd(b, a % b);
}

// 최소공배수
function lcm(a,b){
return a * b / gcd(a,b);
}