프로그래머스 2023.06.02 (2Lv 여러 수의 최소공배수 구하기)
문제 이론 최대공약수(Greatest Common Division) 두 수를 소인수분해를 한 뒤, 두 수의 공통된 소인수를 모두 곱한 것이다. 최소공배수(Least Common Multiple) 두 수를 소인수분해를 한 뒤, 두 수의 모든 소인수를 곱한 것이다. 벤-다이어그램으로 정리하면 아래와 같다. AB = LCM*GCD 유클리드 호제법 A를 B로 나눌 때, 나머지를 R이라하면, GCD(A,B) = GCD(B,R) 이다. 예시 : 60과 24를 나눈 몫은 2이고, 나머지는 12이다. 즉, 60 = 24 * 2 + 12 GCD(60, 24) = GCD(24, 12) = 12 이다. 유클리드 호제법을 이용한 알고리즘 A와 B의 최대 공약수를 구하기 위해서 A를 B로 나눈 나머지 R0을 구한다. B를 R0..
2023. 6. 19.
