최소공배수2 (LEVEL 2)프로그래머스 - N개의 최소공배수(JAVA) 문제 입출력 예 풀이. 1. 유클리드 호제법을 이용하여 gcd함수 구현, lcm함수 구현 2. 0번째 값을 tmp에 저장후 크기만큼 돌며 lcm함수 실행 후 tmp에 해당 값 저장 >> 값 하나씩 비교하며 최대공약수, 최소공배수를 구해준다. class Solution { public int solution(int[] arr) { int tmp = arr[0]; for(int i=0;i 2023. 1. 2. 최대공약수(GCD) 와 최소공배수 (LCM) 최대공약수(GCD : Greatest Common Divisor) 최대공약수는 줄여서 GCD라 불림. 두 수 A,B의 최대공약수 G는 A,B의 공통된 약수 중에서 가장 큰 정수. (약수: N을 나눌수 있는 수) 최대공약수를 빠르게 구하는 방법 - 유클리드 호제법을 사용 GCD(a,b) = GCD(b,r) r이 0이면 그 때 b가 최대 공약수가 된다. ex) GCD(24,8) = GCD(16,8) = GCD(8,0) = 8 최대공약수 구현 재귀함수를 사용한 유클리드 호제법 int gcd(int a, int b){ if(b==0){ return a; } else{ reutnr gcd(b,a%b); } } 세 수의 최대공약수 GCD(a,b,c) = GCD(GCD(a,b),c) N개의 수 도 같은 방식으로 구할.. 2023. 1. 2. 이전 1 다음
