GCD1 최대공약수 최대공약수 특정한 두 수가 주어졌을 때 두 수 의 최대공약수(GCD)를 구하는 코드를 작성한다. 1. 풀이 1.1 풀이 방법 두 수 M과 N의 최대 공약수를 gcd(M, N)이라고 할 때, 다음과 같은 식이 성립한다. (M > N) gcd(M, N) = gcd(N, M % N) (증명은.. 위키에 있다..!) 따라서 위의 식을 M % N = 0이 될 때까지 반복해서 적용한다. M % N = 0이 성립한다는 것은 M이 N의 배수가 된다는 뜻이니까 gcd(M, N) = N이 된다. 1.2 코드 1.2.1 gcd [gcd] private int gcd(int M, int N) { //최대공약수를 구하는 메서드 if (M < N) { int temp = M; M = N; N = temp; } while (M %.. 2022. 8. 9. 이전 1 다음