Algorithm 공부 #12 - 정수론(유클리드 호제법과 확장 유클리드 호제법)

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의 공배수..
Algorithm/알고리즘 공부 일기 2024. 3. 7. 13:58
1
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/01   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함