프로그래머스: Lv1. 최대공약수와 최소공배수

• 문제 설명
  

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

- 최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

ex) 두 수 18, 24
   18의 약수 : 1, 2, 3, 6, 9, 18
   24의 약수 : 1, 2, 3, 4, 6, 8, 12, 24
   공통된 약수는 {1,2,3,6} 이므로 최대공약수는 6 이다.

 

• 최소공배수 LCM(Least Common Mutiple)

- 최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.

- 최소공배수 = 두 수의 곱 / 최대공약수

ex) 두 수 18, 24
   18의 배수 : 18, 36, 54, 72, 90 ...
   24의 약수 : 24, 48, 72, 96 ...
   공통된 배수는 {72, ...} 이므로 최소공배수는 72 이다.

 

위 정의대로 최대공약수를 구하기 위해서는 2부터 두 수중 가장 작은수까지 나누게 되면 최대공약수를 구할 수 있지만, 두 수를 1과 100000과 같은 최악의 케이스로 받았을때는 기본 풀이방법의 대한 효율성이 상당히 떨어진다 할 수 있다. 이를 해결하기 위하여 유클리드 호제법을 사용.

- 유클리드 호제법(Euclidean Algorithm)

기본적인 방법으로 문제를 풀면 시간복잡도는 O(N)이 된다. 나쁜 방법은 아니지만 효율을 높이기 위해 유클리드 호제법이란 알고리즘을 사용하면 시간복잡도를 O(logN)으로 줄일 수 있다.

2개의 자연수  a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단 a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r0를 구하고, 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

ex) 18과 24의 최대공약수 (단, 큰값과 작은값은 항상 먼저 구별!! a=24, b=18)

SEQ	GCD(a,b)	a	b	a%b
1	GCD(24,18)	24	18	6
2	GCD(18,6)	18	6	0

유클리드 호제법을 사용하여 재귀호출을 한 뒤 a%b 계산이 0이 되는순간에 b값이 최대공약수가 된다.

- 풀이

import java.util.Arrays;

public class GcdLcm {
	public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        int gcd = gcd(m,n); //재귀적 호출을 이용하여 최대공약수 구하는 메서드.
        
        answer[0]=gcd;
        answer[1]=(n*m)/gcd;
        return answer;
    }
	//n:작은 수, m:큰 수 
	private int gcd(int m, int n) {
		//n이 0이면 큰 수 m이 최대공약수가 된다.
		if(n==0) {
			return m;
		}
		//n이 0이 될때까지 재귀적 호출로 m%n을 수행하여 (작은수,두수를나눈나머지)형태로 진행된다.
		return gcd(n,m%n);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		GcdLcm gl = new GcdLcm();
		System.out.println(Arrays.toString(gl.solution(3, 12)));
	}

}

 

출처

ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95