728x90 최소공배수 썸네일형 리스트형 [백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python [백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 이번 문제는 주어진 두 수에 대한 최대공약수와 최소공배수를 구하는 문제이다. 이전에도 풀었던 문제인데 코드를 비교해보니 거의 같았다. 공식이 있어서 그런 것 같다. 최대공약수를 구하는 공식은 유클리드 호제법이다. 유클리도 호제법을 이용하면 다음과 같은 공식이 나오게 된다. 두 수 A와 B가 있을 때, A에 대하여 B를 나눈 몫이 X, 나머지가 R이라 하면, "A = B * X + R"의 식이 나오게 .. 더보기 [백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python [백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수(GCD : Greatest Common Divisor)와 최소공배수(LCM : Least Common Multiple)를 구하는 문제다. 이 문제는 유클리드 호제법을 알고 있으면 쉽게 풀 수 있는 문제이다. 유클리드 호제법은 GCD를 쉽게 구할 수 있는 알고리즘 중의 하나이다. 이 알고리즘은 식을 간결하게 해주는 특징이 있다. 두 수 a와 b (a > b)가 있다고 할 때, a와 b의 최대.. 더보기 이전 1 다음