숙명1

• 

  최대공배수_최대공약수(유클리드 호제법(암기)) www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 유클리드 호제법은 2개의 자연수에 대한 최대공약수를 구하는 알고리즘이다. 호제법이란? => 두 수가 서로 상대방 수를 나누어서 최대공약수를 얻는 것이다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다... Algorithm/AlgorihmFoundation 2020. 12. 19.