[코딩 팁] 최대공약수 : 유클리드 호제법 원리

✍️ 최대공약수와 유클리드 호제법 코딩 테스트에서 심심치 않게 등장하는 최대공약수 구하기 2부터 시작하는 반복문으로 구할 수 있지만 유클리드 호제법을 사용하면 보다 효율적으로 구할 수 있다. 유클리드 호제법의 과정은 다음과 같다. 1. 큰 수를 작은 수로 나눈다. 2. 나누는 수를 나머지로 계속 나눈다. 3. 나머지가 0이 나오면 나누는 수가 최대공약수이다. $1512$와 $1008$의 최대공약수를 유클리드 호제법으로 풀어보면 $1512 = 1008 * 1 + 504$ $1008 = 504 * 2 + 0 $ 두 수의 최대공약수는 504이다. 💡 유클리드 호제법 이해하기 나는 원리를 알지 못한다면 금방 까먹는 사람으로서... 대충이라도 원리를 정리해 보려 한다. (1) 어떤 수 $A$를 $B$로 나눈다면 ..