최대공약수
Euclidean algorithm(유클리드 호제법)
Euclidean Algorithm 유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a,b에서 a를 b로 나눈 나머지를 r이라고 했을때 GCD(a,b) = GCD(b, r)과 같게 되고 r이 0이 될때의 b의 값이 최대공약수가 된다. 일반적으로 쉽게 생각할 수 있는 최대공약수를 구하는 방법은 모든 자연수를 나눠보는 것이다. 하지만 이경우 시간복잡도는 O(n)이 된다. 다만 이 유클리드 호제법을 사용할 경우 O(logN)이 되어 더 빠른 속도를 나타낼 수 있다. Greatest Common Divisor(GCD) 2개의 자연수의 공통된 약수인 공약수 중 가장 큰 공약수가 최대공약수이다. 소스코드 ※ 아래 코드는 a>b 를 만족함을 가정 > C++ int gcd(int a,..
BaekJoon(1850)::최대공약수
문제 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 문제 파악 : 1로 이루어진 수의 최대공약수는 두 수의 길이의 최대공약수가 해당 공약수의 길이가 되며 그 공약수 또한 1로 이루어지게 된다. : 왜냐하면 두 수는 1로 이루어져 있기 때문에 위와 같은 이해가 만들어진다. 예시 1, 11, 111, 1111 → 1 11, 1111, 111111 → 11, 1111 문제풀이 : 두 수의 길이의 최대공약수를 구하면 그 값이 주어진 두수의 최대공약수의 길이가 된다. #include #inclu..