JAVA 알고리즘 - N개의 최소공배수 구하기

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.


제한 사항

arr은 길이 1이상, 15이하인 배열입니다.

arr의 원소는 100 이하인 자연수입니다.


문제풀이

공약수란 두 수의 또는 여러 수의 공통인 약수 라는 뜻이다.

최대공약수란?

- 가장 큰 공약수

- 공약수이자, 모든 공약수의 배수인 양의 정수

- 재귀적 정의는 gcd ( gcd ( gcd(n1, n2), n3 ), n4 ) ...

그냥,,,, gcd(n1, n2) 로 암기하자.


최소공배수란?

두 수의 또는 공통되는 두 수의 배수 라는 뜻입니다.

최소공배수를 구하는 방법은 공약수로 나누어서 곱하는 방법이 있습니다.

lcm = a*b / 최대공약수;


  1. package com.education.solution.chap01;
  2. import java.util.Arrays;
  3. /**
  4. * N개의 최소공배수 구하기
  5. * @author user
  6. *
  7. */
  8. public class LcmGcd {
  9. public static void main(String[] args) {
  10. int[] arr = {2, 6, 8, 14};
  11. int answer = 0;
  12. Arrays.parallelSort(arr);
  13. int tmp = arr[0];
  14. for ( int i=0; i<arr.length; i++ ) {
  15. tmp = lcm(tmp, arr[i]);
  16. }
  17. answer = tmp;
  18. System.out.println(answer);
  19. }
  20. /**
  21. * 최소공배수 구하기
  22. * 알고리즘 문제에서 가장 많이 쓰이는 식인데
  23. * 최소공배수 = 두수의 곱 / 두수의 최대공약수
  24. */
  25. static int lcm( int a, int b ) {
  26. return a*b / gcd(a, b);
  27. }
  28. /**
  29. * 최대공약수 구하기
  30. * a%b = b가 0이 아닐때까지 나눠서 a를 리턴한다.
  31. * 두수가 있으면 처음에 그 중 한 수(여기서는 b)로 나누고 나머지를 임시 변수(c)에 저장하고 나누어진수(a)는 나눈수(b)가 되고 나눈수(b)는 임시변수(r)이 된다.
  32. * 그리고 b가 0이 아닐때 까지 반복하다 0이 되면 a를 return 하게 되는데 a가 a,b의 최대공약수가 된다.
  33. */
  34. static int gcd( int a, int b ) {
  35. while (b!=0) {
  36. int c = a%b;
  37. a=b;
  38. b=c;
  39. }
  40. return a;
  41. }
  42. }
* 파트너스 활동을 통해 일정액의 수수료를 제공받을 수 있음
작성자 소개
최찬희 프로필
WrapUp 블로거

최찬희

반려견을 좋아하고, 차를 좋아하고, 여행을 좋아하고, 맛집을 찾아 즐기는 웹 개발자 입니다^^

댓글작성

작성자의 다른 포스팅