No1658 : 최대공약수와 최소공배수 구하기

문제

입력 / 출력 형식

 

• 첫 번째 방법 : 기본적인 방식

• 최대공약수(gcd)란? - 두 수 이상의 공통인 약수(공약수) 중 가장 큰 수
• 8, 12의 공약수 : 1, 2, 4   최대공약수 : 4
• 최소공배수(lcm)란? - 두 수 이상의 공통인 배수(공배수) 중 가장 작은 수
• 8, 12의 공배수 : 24, 48 ...   최소공배수 : 24

import java.util.Scanner;


public class No1658
{
	
	static int gcd_get(int x,int y) {
		int i;
		int ans=0;
		for(i=1;i<=x;i++) {
			if(x%i==0 && y%i==0) {
				ans = i;
			}
		}return ans;
	}

	public static void main(String[] args)
	{
		// 최대공약수 최소공배수
		Scanner in = new Scanner(System.in);
		
		No1658 gcd = new No1658();
		int n1;
		int n2;
		int lcm;
		
		
		n1 = in.nextInt();
		n2 = in.nextInt();
		lcm = 0;
		
		
		System.out.println(gcd_get(n1, n2));
		lcm = (n1*n2)/gcd.gcd_get(n1, n2);
		System.out.println();
		
		
		}

}

 

코드분석

두 값 중 작은 수만큼 반복문을 통해서 공약수를 찾아줘야 한다.

두 수 모두 %i == 0 의 조건을 충족해야 공약수가 됨.

공배수를 구하는 방법도 간단하다. 두 수를 곱한 값에 최소공약수를 나눠주면 최소공배수가 나온다.

따라서 gcd = gcd_get(a, b);  lcm = a * b / gcd;의 식이 나온다.

그러나 위 코드는 매우 큰 값이 들어올 경우 시간초과를 낼 수도 있으니 유클리제 호제법을 이용해서 코드를 짤 수 있다.

 

•  두 번째 방법 : 유클리드 호제법

• 유클리드 호제법이란? - A를 B로 나눈 나머지가 r이라면 A와 B의 최대공약수는 B와 r의 최대공약수와 같다.
• GCD(A, B) = GCD(B, r)
• GCD(30, 18) = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) => 최대공약수 6

import java.util.Scanner;

public class No1658
{
	
	static int euclidean(int x,int y) {
		int r;
		while(y!=0) {
			r = x%y;
			x = y;
			y = r;
		}
		return x;
	}

	public static void main(String[] args)
	{
		// 최대공약수 최소공배수
		Scanner in = new Scanner(System.in);
		
		No1658 gcd = new No1658();
		int n1;
		int n2;
		int lcm;
		
		
		n1 = in.nextInt();
		n2 = in.nextInt();
		lcm = 0;
		
		//유클리드 호제법 
		System.out.println(euclidean(n1, n2));
		lcm = (n1*n2)/gcd.euclidean(n1, n2);
		System.out.println(lcm); 
		
		
		}

}

 

코드분석

두 수 중 더 작은 값을 두 수를 나눈 나머지로 나머지가 0이 나올 때까지 계속해서 나누면 최대공약수가 나오게 된다.

x와 y의 자리를 y, r의 값으로 반복해서 바꿔주면서 값을 구해냈다.

공배수를 구하는 방법은 1번 방법과 동일하게 적용했다.

위 코드를 재귀적 방법으로 더 간편하게 바꿀 수 있다.

 

 

• 재귀적 방법

import java.util.Scanner;

public class No1658
{
	
	static int recursive(int x,int y) {
		
		if(y==0) return x;	// y=0이면 최대 공약수는 x가 됨. 재귀는 끝나는 포인트를 꼭 지정해줘야함.
		return recursive(y, x%y);  // 재귀적호출. 본인을 계속해서 호출.
	}

	public static void main(String[] args)
	{
		// 최대공약수 최소공배수
		Scanner in = new Scanner(System.in);
		
		No1658 gcd = new No1658();
		int n1;
		int n2;
		int lcm;
		
		
		n1 = in.nextInt();
		n2 = in.nextInt();
		lcm = 0;
		
		//재귀적 용법 
		System.out.println(recursive(n1, n2));
		lcm = (n1*n2)/gcd.recursive(n1, n2);
		System.out.println(lcm);
		
		
		}

}

 

코드분석

유클리드 호제법을 코드만 재귀적으로 바꾼 방법이다.

(x,y)라고 할때 x의 자리에는 y가, y의 자리에는 x%y가 들어가야하고 (x,y)에서 y의 자리에 0이 들어가면 계산이 끝나게 된다.

재귀적 용법을 사용할 때는 꼭 자기자신의 호출을 끝내는 포인트가 있어야 한다.

 

리뷰

처음 재귀 알고리즘을 배웠을 때는 아주 간단한 피보나치 수열 코드조차도 이해하기 어려웠고, 생각을 하면 할수록 머리가 아파오는 것 같았다. 물론 내가 내 힘으로 재귀를 이용한 코드를 짜는건 상상도 못할 일이였다.

물론 지금도 아주 기초적인 내용이고 복잡하지 않은 부분이지만, 불과 몇 주 전을 생각해보면 이조차도 대단한 발전이라고 생각이 든다.

유클리드 호제법이라는 방법도 오늘 처음으로 알게 됐다. 처음에는 설명을 봐도 이해가 잘 안 갔는데 차근차근 생각해보니 어려운 개념이 아니라는 것을 알게 됐다. 코드에 분석하는 것도 생각보다 어렵지 않고 오히려 더 단순해서 신기했다.

매일매일 느리지만 조금씩 성장해 나가고 있다고 생각하고, 1년 뒤에는 어엿한 주니어 개발자로서 업그레이드 되어 있으면 좋겠다.