학교에서 배운 최대공배수 구하는 방법과유클리드 호제법 알고리즘을 사용해서 코드를 구현하는 방법은 다르다. 나처럼 유클리드 호제법이 뭔데? 라고 생각한 분들을 위해5분 안에 쉽게 이해되도록 설명해보겠다. 최소공배수를 구하는 공식에 최대공약수가 들어가므로최대공약수 먼저 알아보겠다.  ※ 유클리드 호제법 - 최대 공약수 유클리드 호제법은 두 자연수의 최대 공약수를 구하는 알고리즘이다.먼저 MOD 연산을 알고 있어야 하는데 MOD는 두 수의 나머지를 구하는 연산이다.예를 들어 파이썬에서 나머지를 구하는 연산은 % 이며, 10 % 6 = 4 가 나온다. 유클리드 호제법으로 108과 138의 최대공약수를 구해보겠다.이해하기 쉽게 그림으로 풀어봤다.  1. 큰 수를 작은 수로 MOD 연산 실행2. 전 단계에서의 작은..

https://www.acmicpc.net/problem/1934 백준 1934번 최소공배수 문제를 풀려면 먼저유클리드 호제법 최대공약수에 대해 알아야 한다. 유클리드 호제법에 대한 세세한 내용은 알고리즘 카테고리에 기록해 놨다.  문제   풀이 자연수 A와 B가 입력되었을 때 최소공배수의 공식은 "A*B / 최대공약수"이다.아래 그림은 두 번째 케이스의 gcd(6, 10)을 구하는 방법이다.  큰 수를 작은 수로 나누는 MOD 연산을 한 후,전 단계에서의 작은 수와 결과값 나머지를 다시 MOD 연산을 한다.재귀 함수로 결과값이 0이 될 때까지 반복 수행한 후,나머지가 0이 되는 순간의 작은 수가 두 수 A, B의 최대 공약수이다. 1934번 문제는 최소 공배수를 구하는 문제이다.앞서 최소 공배수의 공식..