백준 2609 [최대공약수와 최소공배수]

 

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

---

 

package deffender_study;
import java.util.*;

public class Main{
	public static void main(String args[]){
		Scanner scan=new Scanner(System.in);
		int a,b;
		System.out.print("두 자연수 입력하라: ");
		a = scan.nextInt();
		b = scan.nextInt();
		
		int max; //두 수 중 더 큰 값을 찾기
		if(a>b) { max = a; }
		else { max = b; }
		
		int gcd = 0;
		for(int i=1; i<= max/2; i++) {
			if(a%i == 0 && b%i == 0) {
				gcd = i;
			}
		}
		int lcm = a*b/gcd;
		System.out.println("최대공약수는 " + gcd);
		System.out.println("최소공배수는 " + lcm);
	}
}	

이거는 비교적 쉽게 풀린 문제라고 생각하는데...

제출시간이 4분이나 지났는데 결과가 아직도 안뜨는 거 보면 별로 효율적이진 못한 코드인건가///

 헉 틀렸다.. 답은 나오긴 하는데 잘못된 코드인건가

 

---

package deffender_study;
import java.util.*;

public class Main{


	public static void main(String args[]){
		Scanner scan=new Scanner(System.in);
		int a,b;
		System.out.print("두 자연수 입력하라: ");
		a = scan.nextInt();
		b = scan.nextInt();
		
		int max, min; //큰 수와 작은 수를 분류하기
		if(a>b) { max = a; min = b;}
		else { max = b; min = a;}
		
		int g; //최대공약수
		int tmp;
		while(true) {
			if(max % min == 0) {
				g = min;
				break;
			}
			else {
				tmp=max%min;
				max=min;
				min=tmp;
			}
		}
		
		int l = a*b/g; //최소공배수
		System.out.println("최대공약수는 " + g);
		System.out.println("최소공배수는 " + l);
	}
}	

유클리드 호제법에 대해서 공부한 뒤 코드를 짜봤다. 맞았습니다!! 너무 뿌듯한 말...

이 코드가 왜 수학으로 분류됐는지 이제 알 것 같다...!

그래도 새로운 알고리즘을 배운 것 같아서 좋음

---

package deffender_study;
import java.util.*;

public class Main{


	public static void main(String args[]){
		Scanner scan=new Scanner(System.in);
		int a,b;
		System.out.print("두 자연수 입력하라: ");
		a = scan.nextInt();
		b = scan.nextInt();
		
		int max, min; //큰 수와 작은 수를 분류하기
		if(a>b) { max = a; min = b;}
		else { max = b; min = a;}
		
		int g = 0; //최대공약수
		int tmp;
		while(g != min) {
			if(max % min == 0) {
				g = min;
			}
			else {
				tmp=max%min;
				max=min;
				min=tmp;
			}
		}
		
		int l = a*b/g; //최소공배수
		System.out.println("최대공약수는 " + g);
		System.out.println("최소공배수는 " + l);
	}
}	

while문의 무한반복을 빼고 싶어서 코드를 다시 짜봤다!

한결 더 효율적인 코드가 됐길...

---

유클리드 호제법?

두 수의 최대공약수를 구하는 알고리즘!

 

호제법이란?

두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다!

 

MOD연산이란?

두 값을 나눈 나머지를 구하는 연산!

 

유클리드 호제법에 대한 이해를 돕는 증명을 설명해주심!! (이해 쏙쏙 잘됨)

https://www.youtube.com/watch?v=J5Yl2kHPAY4

 

유클리드 호제법에 대해서 잘 설명해주심

https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

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