최대공약수와 최소공배수 / 프로그래머스 연습문제 / programmers / level1 / Java

https://programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

---

이번문제는 사실 수학문제와 같다.

 

최대공약수와 최소공배수를 구하는 공식을 알면 코드를 쉽게 풀 수 있다.

물론 나는 수학이 많이 약했기에... 구글링으로 공식들이 어떤식으로 이루어지는지 찾아보았다.

 

일단 최대공약수 최소공배수라는 것은,

 

최대공약수 (GCD: Greatest Common Divisor)

• 두 정수의 공약수 중에서 가장 큰수 (공약수란 두 숫자 모두 나누어 떨어지는 수를 말한다.)

최소공배수 (LCM: Least Common Multiple)

• 두 정수의 공부새 중에서 가장 작은수 (공배수란 두 숫자가 곱해서 나올 수 있는 같은 숫자를 말한다.)

라고 하며 그 중 유클리드 호제법이라는 알고리즘을 이용하여 최대공약수를 구하였다.

 

유클리드 호제법 (Euclidean Algorithm)

• 최대공약수를 구하는 컴퓨터 프로그래밍에서 가장 많이 사용하는 알고리즘 중 하나
• 호제법이란 두 수가 서로 상대방의 수를 나누어서 원하는 수를 얻는다는 의미
• 예를 들어 2002와 1004의 최대 공약수를 해당 알고리즘을 이용하여 구한다고 한다면

2002 = 1004 x 1 + 998
1004 = 998 x 1 + 6
998 = 6 x 166 + 2
6 = 2 x 3 + 0
최대공약수 = 2 (이런식으로 계산하는 방법이다.)

 

그리고 두 수를 곱한 값을 최대공약수로 나누면 최소공배수가 된다.

2002 x 1004 / 2 = 1,005,004

 

그걸 바로 코드로 적용해본다.

 

[작성코드]

public class gcdicm {

	public static void main(String[] args) {
		solution(2002, 1004);	
	}

    public static int[] solution(int n, int m) {
        int[] answer = new int [2];

        int max = gcd(n , m);
        int min = icm(n , m);

        answer[0] = max;
        answer[1] = min;
        System.out.println(answer[0]);
        System.out.println(answer[1]);
        return answer;
    }
	
	public static int gcd(int a, int b) {
		while (b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}

	public static int icm(int a, int b) {
		return a * b / gcd(a, b);
	}

}

수학 공부 더 열심히 해야겠다.

---

[깃허브 링크]

https://github.com/RUCKUSJERRY/practiceOfAlgorithm/blob/main/Prs_Pratice/src/com/level01/gcdicm.java

RUCKUSJERRY/practiceOfAlgorithm