알고리즘/코드 저장2 [JAVA] 최대공약수, 최소공배수 찾기 가장 기초적인 방식으로 최대공약수를 구하는 방법은 큰 수부터 차례대로 나누는 것이고, 최소 공배수는 두 수 중 작은 수부터 시작해 동시에 나누어지는 수를 검사하는 방식이다. 하지만 이러한 방법은 두 수가 모두 소수이면 오랜 시간이 소모될 수 있다. 그래서 최대공약수와 최소공배수를 효율적으로 구하기 위해 유클리드 호제법을 사용할 수 있다. int uclid(int a, int b) { if (b==0) return a; return uclid(b, a%b); } 추가로 간혹 유클리드 호제법을 사용해도 풀리지 않는 알고리즘 문제들이 존재한다. 이럴 때는 확장 유클리드 호제법을 사용하면 된다. int extUclid(int a, int b, Integer[] x, Integer[] y) { int g = a;.. 2020. 4. 4. [JAVA] 소수 찾기 소수란 1과 자기 자신을 제외하고는 약수가 없는 수이다. 소수를 찾는 가장 기초적인 방법은 2~n-1 까지 반복문을 돌리거나, 혹은 2~n/2 까지 반복문을 돌리며 나누어봄으로써 소수를 찾을 수 있겠지만, 당연히 이는 효율적이지 못한 방법이다. 하지만 아래의 방법을 사용하면 않고 √n까지 나누면 소수인지 알 수가 있다. 이 방법은 O(√n)의 시간 복잡도를 가진다. boolean isPrime(int n) { if(n 2020. 4. 4. 이전 1 다음