유클리드 호제법

[프로그래머스] N개의 최소공배수 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 유클리드 호제법 풀이 [2, 6, 8, 14] 가 있다면 2와 6의 최소공배수 = 6, 6와 8의 최소공배수 = 24 24와 14의 최소공배수 = 168 이 된다. 즉 모든 수에 대해 현재까지 구한 최소공배수와 다음 수의 최소공배수를 구해 현재까지 구한 최소공배수를 갱신하면 된다. a 와 b의 최소공배수는 a * b / (a와 b의 최대공약수) 로 구할 수 있고, a 와 b의 최대공약수는 유클리드 호제법을 이용하여 구할 수 있다. 코드 class Solution { public int solut..

[프로그래머스] 최대공약수와 최소공배수 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 유클리드 호제법 풀이 유클리드 호제법을 이용해 두 수의 최대공약수를 구하고, 두 수의 곱을 최대공약수로 나눠 최소공배수를 구한다. 코드 class Solution { public int[] solution(int n, int m) { int gcd = getGcd(n, m); int lcm = n / gcd * m; return new int[] { gcd, lcm }; } public int getGcd(int a, int b) { if (a < b) { int tmp = a; a = b; b..

[프로그래머스] 유한소수 판별하기 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 유클리드 호제법 풀이 유클리드 호제법을 이용해 최대 공약수를 구하고, 분모를 최대 공약수로 나눈 값을 5와 2로 가능한만큼 나눈 후 그 값이 1이면 1, 아니면 2를 출력한다. 코드 class Solution { public int solution(int a, int b) { b /= getGCD(a,b); while(b % 5 == 0) b /= 5; while(b % 2 == 0) b /= 2; if(b == 1) return 1; else return 2; } int getGCD(int n..

[프로그래머스] 분수의 덧셈 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 유클리드 호제법 풀이 기약 분수는 두 분수를 통분한 뒤, 분자와 분모를 둘의 최대공약수로 나눠 구할 수 있다. 최대공약수를 구하기 위해 유클리드 호제법을 사용했다. 코드 class Solution { public int[] solution(int denum1, int num1, int denum2, int num2) { int denum3 = denum1 * num2 + denum2 * num1; int num3 = num1 * num2; int gcd = getGcd(denum3, num3);..

[백준] 1735. 분수 합 (Java)

🔒 문제 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 🔑 알고리즘 유클리드 호제법 💡 풀이 어떤 분수를 기약 분수로 만드는 방법은 분자와 분모를 둘의 최대 공약수로 나누는 것이다. 최대 공약수는 유클리드 호제법을 이용하여 쉽게 구할 수 있다. ✏️ 코드 import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.IOException; public class Main { public static void main(St..

[백준] 9613. GCD 합 (Java)

🔒 문제 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 🔑 알고리즘 유클리드 호제법 💡 풀이 문제에서 주어진대로 각 쌍마다 최대공약수를 계산해 더한다. 최대공약수를 구하는데 유클리드 호제법을 이용한다. * n이 100이고 모든 값이 1,000,000 이라면 sum의 값은 100C2 * 1,000,000 = 4,950 * 1,000,000 = 4,950,000,000 로 int 범위를 초과하므로 long 자료형을 사용한다. ✏️ 코드 import java.io.BufferedReader..