프로그래머스 (1) 썸네일형 리스트형 [알고리즘] 유클리드 호제법 / 최대공약수 2개의 자연수 or 최대공약수를 구하는 알고리즘 중 하나 2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같음 최대공약수를 구하는 일반적 방법 소인수분해를 통해 두 수의 최대공약수를 구하기 위해서 사용 -> 두 수를 소인수분해 한 후, 공통 소수를 찾음 그러나, 숫자가 커질수록 소인수분해 하기 어려움 MOD연산 두 값을 나눈 나머지를 구하는 연산 유클리드 호제법은 MOD연산의 반복 나머지가 0이 되었을 때, 마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수 1112 mod 695 = 417 695 mod 417 = 278 417 mod 278 =139 278 mod 139 = 0 * 두 수에 대한 유클리드 호제법.. 이전 1 다음