Algorithm

[Algorithm] 유클리드 호제법

유클리드 호제법이란? 2개의 자연수의 최대공약수를 구할 수 있는 공식으로 명시적으로 기술된 가장 오래된 알고리즘이다. 호제법(互除法)이란 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻어낸다는 의미이다. 정리 두 수 a, b가 있다고 가정해보자. (a > b) 큰 수(a)를 작은 수(b)로 나눴을 때 나머지 값이 0이 되면, 나눴던 수 중 작은 수(b)가 최대공약수가 된다. 0이 되지 않는다면 작은 수(b)가 큰 수가 되고, 나머지 값(c)이 작은 수가 된다. 작은 수(b)에 나머지 값(c)을 나누는 식으로 나머지가 0이 될 때까지 반복한다. 나머지가 0이 되면, 나누었던 두 수 중 작은 수가 최대공약수가 된다. Javascript 예시 문법 function solution(n, m) { le..