최대공약수, 최소공배수 (feat. 유클리드 호제법)
2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 위의 문제를 구현하다 더 쉽게 최대공약수와 최소공배수를 구하는 방법을 알게 되어 작성한다. 최대공약수 구하는 방법 방법 1: 각 수의 약수를 구한 후 공통되는 최대값 찾기 위의 문제를 풀면서 처음 생각한 방법이다. 예를 들어 18과 24의 최대공약수를 구해야한다. 18의 약수: 1, 2, 3, 6, 9, 18 24의 약수: 1, 2, 3, 4, 6, 8, 12, 24 이들의 공약수는 1, 2, 3, 6이고 가장 큰 값인 6이 최대공약수가 된다. 약수 알고리즘 (Java) 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때..
2023. 5. 18.
