101 일차 - HA 3 알고리즘 후기 + 유클리드 호제법

HA 3 중 첫 째날 알고리즘 테스트를 제출 완료했다.

알고리즘 테스트는 항상 난이도가 높지 않았아서 걱정은 별로 하지 않았는데, 이번 알고리즘 테스트는 너무 쉬웠다.
테스트를 시작하고 사이트에 접속이 되지 않아 10분이 지연되었는데 정작 테스트를 시작하고 20분 만에 제출을 완료했다.
그래서 시험 언급에 대해서는 무의미할 것 같고, 어제 공부한 유클리드 호제법을 정리하는 시간을 가져보려고 한다.

유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법은 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법이다.
유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다.

그 예시는 아래와 같다.

1071과 1029의 최대공약수를 구하면
1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. -> 42
1029는 42로 나누어 떨저지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다 -> 21
42는 21로 나누어 떨어진다.
따라서, 최대 공약수는 21이다.

보기 쉽게 표현해 보면
1071 = 1029 1 + 42
1029 = 42 24 + 21
42 = 21 * 2 + 0

최대 공약수는 21

이 식을 자바스크립트로 표현하면 아래와 같다.

function gcd(m, n) {
  // 탈출 조건
  if (m % n === 0) return n;
  // 나머지가 0이 아니면 다음 단계로
  return gcd(n, m % n);
}

1071과 1029를 넣어서 식을 돌려보면 같은 결과가 나온다는 것을 볼 수 있고 작동원리도 자세히 볼 수 있다.

자료 출처:
나무위키 - 유클리드 호제법
위키백과 - 유클리드 호제법