푸으름

Algorithm 공부 #27 - 확장 유클리드 호제법  ✏️ 유클리드 호제법최대공약수 관련 문제들을 풀어봤다면 한번쯤은 접해 봤을 법한 알고리즘자연수 a와 b가 주어졌을 때 gcd(a,b) 즉 a와 b의 최대공약수를 구할 수 있음 a를 b로 나눈 몫을 q라고 하고, 나머지를 r이라 하면 a= bq + r로 나타냄이때 gcd(a,b) = gcd(b,r)을 만족 gcd(a,b)=g">gcd(a,b)=ggcd(a,b)=g라고 하면, g|a">g|ag|a, g|b">g|bg|b 를 만족하게 되고, r=a−bq">r=a−bqr=a−bq이므로 g|(a−bq)=r">g|(a−bq)=rg|(a−bq)=r 을 만족gcd(b,r)=g">gcd(b,r)=ggcd(b,r)=g라고 해도, g|b">g..

Algorithm 공부 #12 - 정수론(유클리드 호제법과 확장 유클리드 호제법) 유클리드 호제법(최대 공약수 구하기) ● 큰 수를 작은 수로 나누는 MOD연산 ● 앞 단계에서 나왔던 작은 수와 나머지를 다시 MOD연산 ● 이렇게 반복하면서 나머지가 0이 되면 그 순간의 작은 수를 최대 공약수로 선택 ex) 270과 192 270 mod 192 = 78 192 mod 78 = 36 78 mod 36 = 6 36 mod 6 = 0 => 0이 되는 순간 6을 return, 즉 270과 192의 최대공약수는 6 백준 1934번 최소공배수 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수..