728x90 최대공약수 썸네일형 리스트형 [백준알고리즘] 1850번: 최대공약수 -Python [백준알고리즘] 1850번: 최대공약수 -Python https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. www.acmicpc.net 예제를 헷갈릴만하게 줬다. 처음에 보면 두 수의 차이만큼 1이 존재하는 것처럼 느껴진다. 하지만 뭔가 이상해서 생각해보니 두 수의 최대공약수만큼 1이 존재하는 것과 같았다. 두 수의 차이만큼 1이 존재하는 것이 아닌 것은 다음을 보면 알 수 있다. 입력으로.. 더보기 [백준알고리즘] 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 다음