지난 글 : [알고리즘/알고리즘 도감] - k-means 알고리즘
유클리드(Euclidean) 알고리즘은 두 수의 최대공약수를 구하는 알고리즘으로서 세계에서 가장 오래된 알고리즘으로 유명하다. 언제 발견됐는지는 알 수 없지만, 가장 오래된 기록이 기원전 300년에 작성된 유클리드 필서라는 것에서 유클리드라는 명칭이 붙여졌다.
1
유클리드 알고리즘으로 1112와 695의 최대공약수를 계산하기에 앞서 수기로 계산해보자.
1. 일반적인 방법으로 두 개의 수를 소인수분해해 공통되는 소수를 최대공약수로 구한다.
1112 = 139 X 2 X 2 X 2
695 = 139 X 5
139 = 최대공약수
2. 하지만 이 방법에서는 두 수가 커질수록 소인수분해가 어려워진다. 유클리드 알고리즘에서는 더
효율적으로 최대공약수를 구할 수 있다.
2
유클리드 알고리즘의 흐름이다.
1. 먼저 큰 숫자를 작은 숫자로 나눈 나머지를 구한다. //결과 : 1112 mod(%) 695 = 417
2. 이번에는 나눈 수 695와 나머지 417로 mod연산을 한다. //결과 : 695 mod(%) 417 = 278
3. 같은 계산을 반복한다. //417 mod(%) 278 = 139 //278 mod(%) 139 = 0
4. 278과 139로 mod 연산을 하면 0이 나온다. 즉 278은 139로 나누어지며 나머지가 없다.
5. 나머지가 0이 됐을 때 마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수가 된다.
오 신기하다
고대 사람들은 뭘 먹고 살았길래 이리 신기하고 멋진 수식을 만들어 냈나 싶다
참고 서적 :
