유클리드 알고리즘

intro

최대공약수 알고리즘은 아주 쉬운 난이도를 요구하는 알고리즘 이지만,
필자는 계속 최대공약수를 사용하는 문제풀이에서 유클리드 알고리즘을 사용하지 않고,
반복문의 풀이를 사용함으로써 코드 작성에서 효율성을 얻고자 상기하는 겸 이 글을 작성합니다!

what is 유클리드 호제법?

유클리드 알고리즘은 두 자연수 사이의 최대공약수를 구하는 알고리즘이다.
명시적으로는 가장 오래된 알고리즘이라고 알려져 있다.

1.두 수 중에서 큰 수를 작은 수로 나눈다.
2.만약 나누고 난 나머지가 0 이라면 작은 수가 최대 공약수이다.
3.만약 나누고 난 나머지가 0이 아니라면, 작은 수를 다시 나머지로 나눈다.
4.이를 반복하고 나머지가 0이 되면, 그 수가 바로 두 수의 최대공약수이다.

function gcd(a,b) {
	const remain = a%b  		// 1번
  if ( remain === 0) return b // 2번
  return gcd(b,remain)		// 3번
}

만약 a = 12
b = 21 이라고 했을 때

12 % 21 은 0이 아니다.
return gcd(21,12)
21 & 12 은 0이 아니다.
return gcd(12,9)
12 % 9 은 0이 아니다.
return gcd(9,3)
9 % 3 은 0이다.  
==> 3이 최대 공약수이다.

두 수중에서 큰 수를 작은 수로 나눈다고 했는데, 위의 코드에서는 그 과정이 빠져있습니다. 이는 어떤 수를 자신보다 더 큰 수로 나누게 되면 몫이 0이 되고 그 자신이 나머지가 되는 것을 응용한 것입니다. (위의 예시를 보면 이해할 수 있다.)