유클리드 호제법 두 수의 최대 공약수를 구하는 알고리즘으로, 코딩 테스트에서는 재귀 형태로 구현된다 과정 큰 수를 작은 수로 나누는 MOD 연산을 수행한다 MOD 연산 : 두 값을 나눈 나머지를 구하는 연산 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)로 MOD 연산을 수행한다 앞 단계를 반복하다가 나머지가 0이 되는 순간의 작은 수 = 최대 공약수 최소 공배수도 구할 수 있다 최소 공배수 = a * b / 최대 공약수 확장 유클리드 호제법 : 방정식의 해 구하기 방정식 : ax + by = c 단 a,b,x,y,c는 정수 c는 최대 공약수 gcd(a,b)의 배수 백준 9613번 풀이(python) 과정 input 재정의 및 t 입력받기 GCD 함수 구현 나머지가 0이면 작은 수 출력 나머지가 0..
