[level1, 유클리드 호제법] 최대공약수와 최소공배수

1. 문제

 

 

 

 

 

 

2. 문제 해결 논리

1. 문제 이해
   • 주어진 것
     • int n, int m    //임의의 두 자연수
   • 요구되는 것
     • 두 수의 최대공약수(GCD) 최소공배수(LCM)
2. 데이터 구조 결정
   • 유클리드 호제법
     • 기본 원리
       • 두 수의 GCD(최대공약수, Greatest Common Divisor)를 찾는 알고리즘
       • 두 양의 정수 a와 b(a > b)가 주어졌을 때, a를 b로 나눈 나머지 r과 b의 GCD는 같다
       • 얻어진 b와 r(b > r)로 b를 r로 나누면 나머지 r2와 r의 GCD는 같다
       • 이와 같은 작업을 반복하여 나머지가 0이 되는 시점에서 나누는 수가 GCD
     • 방법 1. 반복문 사용
     • 방법 2. 재귀 호출 사용
       • 코드가 간결하고 이해하기 쉬움
       • 재귀 호출 횟수가 매우 많아지면 스택 오버플로우가 발생할 가능성이 있음
   • 방법 3. 브루트 포스(Brute Force) 사용
     • 간단하고 이해하기 쉬움
     • 주어진 두 수가 큰 경우, 유클리드 호제법보다 비효율적

 

 

 

 

 

 

3. 코드 구현

 

    3-1. 유클리드 호제법 - 반복문

class Solution {
    public int[] solution(int n, int m) {
        int gcd = gcd(n, m);
        
        //두 수의 곱 = 최소공배수 * 최대공약수
        //위 관계를 사용해서 최소공배수 도출
        int lcm = (n * m) / gcd;
        
        return new int[]{gcd, lcm};
    }
	
    //최대공약수를 구하는 메소드
    public static int gcd(int a, int b) {
    
    	//b가 0이 아닌 경우에 반복
        //b > a인 경우, while문을 한 번 통과했을 때, a와 b가 바뀌어서 a > b의 경우로 넘어감
        //따라서, 다음의 경우는 a > b인 경우, b > a인 경우를 모두 커버함
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        
        //b가 0인 경우 a값 반환
        return a;
    }
}

 

 

 

 

 

    3-2. 유클리드 호제법 - 재귀 호출

class Solution {
    public int[] solution(int n, int m) {
        int gcd = gcd(n, m);
        int lcm = (n * m) / gcd;
        return new int[]{gcd, lcm};
    }

     public static int gcd(int a, int b) {
        
        //b가 0인 경우, a 반환
        if (b == 0) {
            return a;
        }
        
        //b가 0이 아닌 경우, b와 나머지 a % b로 다시 수행
        return gcd(b, a % b);
    }
}

 

 

 

 

 

    3-3. 브루트 포스(Brute Force)

class Solution {
    public int[] solution(int n, int m) {
    	//제일 작은 최대 공약수 1부터 시작
        int gcd = 1;
        
        //n과 m중 작은 값
        int min = Math.min(n, m);
		
        //자연수 2부터 시작하여 
        //n과 m의 최대공약수(작은 값 min을 넘지 않음) 구하기
        for (int i = 2; i <= min; i++) {
            if (n % i == 0 && m % i == 0) {
                gcd = i;
            }
        }
		
        //최소공배수 = (두 수의 곱) / 최대공약수
        int lcm = (n * m) / gcd;

        return new int[]{gcd, lcm};
    }
}

 

 

 

 

 

 

 

 

* Reference

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스