[JAVA][정올 1658] 최대공약수와 최소공배수

사이트명	정올
문제 링크	jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=931&sca=2030
주요 알고리즘	#수학
사용 언어	Java
설명이 장황합니다.. 도움되는 것만 파악하세요 :-)

1. 문제

 

2. 입력 / 출력

 

 

---

3. 풀이

3-1. 생각 노트

최대공약수 GCD : 두 수의 약수 중에서 가장 큰 수

최소공배수 LCM : 두 수의 배수 중에서 가장 작은 수

 

우선,

최대공약수는 유클리드 호제법과 for문으로 처음부터 찾는 방식이 있다.

 

- 유클리드 호제법은 나머지연산(%)을 활용하는 것으로, 나머지가 0이 될 때까지, 나머지와 그 전 수를 계속 나누는 방식이다.

- 노동으로 찾는 방법은 1부터 N까지 나누었을 때, 두 수 모두 나머지가 0이 되어 약수가 되는 수를 찾으면 된다.

 

최대공배수의 경우,

최소공배수 = A * B / 최대공약수

를 활용한다.

 

3-2. 변수명

type	변수명	설명
static	gcd	재귀로 풀었을 때, 최종 결과값을 저장하기 위한 전역변수

 

3-3. 코드 보기

package jungol;

import java.util.Scanner;

public class JO1658_최대공약수와최소공배수 {
	
	static int gcd;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
	
		String[] input = sc.nextLine().split(" ");
		
		int A = Integer.parseInt(input[0]);
		int B = Integer.parseInt(input[1]);
		
		//유클리드 호제법으로 구하기
		euclid(A,B);
		
		//최소공배수 구하기
		int lcm = A * B / gcd;
		
		System.out.println(gcd);
		System.out.println(lcm);
		
	}

	//유클리드 호제법으로 구하기
	private static void euclid(int a, int b) {
		//탈출 조건
		if(a % b == 0) {
			gcd = b;
			return;
		}
		euclid(b , (a%b));
	}
}

 

위에는 유클리드 호제법(재귀)이고, 아래엔 노동으로 푸는 과정이다.

	//일반 방식으로 구하기
  	int normal_gcd = normalGCD(A,B);
	System.out.println(normal_gcd);
    
    //일반 방식으로 구하기
	private static int normalGCD(int a, int b) {
		
		int i, gcd=1;
		
		//두 수 중 어느 하나보다 낮게만 가면 된다.
		//작은수로 하더라도, 그 안에 없으면 공통이 아니기 때문.
		for (i = 1; i <= a; i++) {
			if(a%i == 0 && b%i==0) {
				gcd = i;
			}
		}
		
		return gcd;
	}

 

 

3-4. 마무리

기초적인 부분이라 생각했는데, 이것도 모르는걸 보며 많은 반성을 하게 된다. 알고리즘은 다른 분야다. 프로젝트 개발의 중요성도 있지만 일단 알고리즘 사고력을 갖춰야 더 멀리 갈 수 있다(특히 취업).

 

알고리즘 연습하면서 (분명 배웠겠지만) 잊어버린 수학 공식도 다시 배운다.. 화이팅!