[백준(baekjoon) 2609] 최대공약수, 최소공배수(GCD/LCM) 원리/코드/유클리드 호제법

[백준(baekjoon) 2609] 최대공약수, 최소공배수(GCD/LCM) 원리/코드/유클리드 호제법 문제 백준 2609 최대공약수(GCD) 와 최소공배수(LCM) 를 구하시오. 원리 최대공약수 : 유클리드 호제법 사용 최소공배수 : 최대공약수 활용 유클리드 호제법 GCD(A, B) = A, B의 최대공약수 r = A % B 일 때, GCD(A, B) = GCD(B, r)이다. 단, r == 0이면 GCD(B, r) = B이다. 딱 r = A % B = 0으로, 딱 나누어 떨어지므로 최대공약수는 B 예시 A = 24, B = 82 GCD(24, 82) r = 24 % 82 = 24 r > 0 -> GCD(82, 24)호출 GCD(82, 24) r = 82 % 24 = 10 r > 0 -> GCD(24, ..

2017.11.13