백준: 최대공약수(GCD)와 최소공배수(LCM) 구하는 메소드 (나머지 연산)

문제) 12와 20의 최대공약수를 구하시오

 

어떻게 푸시나요?

​

보통 나눗셈을 합니다

최대공약수 = 2X2 = 4​

하지만 주어진 두 수가 엄청 크다면

어떤 수로 나눠야할지 일일히 찾아야하기 때문에

컴퓨터 연산에서는 비효율적입니다

​

​

최대공약수

A와 B의 나머지 연산으로 최대공약수를 구한다

​

두 수(12, 20)만으로 최대공약수를 구해봅시다​

20 % 12 = 8 (20을 12로 나눈 나머지)

12 % 8 = 4 (12를 8로 나눈 나머지)

8 % 4 = 0 (나머지가 0일 때 그 수는 최대공약수)

​

논리가 매우 단순해졌죠??​

메소드로 만들면 다음과 같습니다

static int GCD(int A, int B) { //B를 A로 나눈 나머지를 구합니다
		if(A==0)return B; // 마지막 나머지가 0이 될때 나눠준 A가 곧 최대공약수입니다 
		return GCD(B%A,A); // A를 다시 나눠줍니다. B를 A로 나눈 나머지로 A를 나눕니다

//A가 B보다 더 크다면? B%A=B가 되고 결국 GCD(B%A,A)가 됩니다. 즉 처음 GCD(A, B)에서 자동정렬된 GCD(B, A)가 됩니다
}

 

이 메소드 안에 12 20을 집어넣으면?

컴퓨터는 이렇게 찾아냅니다!

​

 

최소공배수

A에 1,2,3...N 을 곱해본다

AxN 을 B로 나눈 나머지가 0이 될 때

AxN은 곧 최소공배수이다

​

12와 20의 최소공배수는 어떻게 구할까요?

한 쪽에다 계속 숫자를 곱해 확인합니다

(12 x 1) % 20 = 12

(12 x 2) % 20 = 4

(12 x 3) % 20 = 16

(12 x 4) % 20 = 8

(12 x 5) % 20 = 0

12 x 5 = 60이 최소공배수입니다

​

메소드는 다음과 같습니다

static int LCM(int A, int B, int N) {
		if((A*N)%B==0)return A*N;
		return LCM(A,B,N+1);
}

 

 

Java 전체 코드

import java.util.*;
public class Main {
	 static int GCD(int A, int B) {
			if(A==0)return B;
			return GCD(B%A,A);
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		System.out.println(GCD(A,B));
}}

import java.util.*;
public class Main {
    static int LCM(int A, int B, int N) {
		if((A*N)%B==0)return A*N;
		return LCM(A,B,N+1);
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		System.out.println(LCM(A,B,1));
}}