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

1. 문제

2. 문제 해결 로직

문제 이해
- 주어진 것
  - int n, int m // 임의의 두 자연수
- 필요한 것
  - 두 개의 최대 공약수 (GCD) 최소 공배수 (LCM)
데이터 구조 결정
- 유클리드 호제법
  - 기본 원리
    - 두 개의 GCD(최대 공약수, Greatest Common Divisor)를 찾는 알고리즘
    - 두 개의 양의 정수 a와 b(a>b)가 주어지면, a를 b로 나눈 나머지 r과 b의 GCD는 동일합니다.
    - 얻은 b와 r(b>r)에서 b를 r으로 나눈다면 나머지 r2와 r의 나머지는 동일합니다.
    - 이러한 작업을 반복하고 나머지가 0이 되는 시점으로 나누는 수가 GCD
  - 방법 1. 반복문 사용
  - 방법 2. 재귀 호출 사용
    - 코드가 간결하고 이해하기 쉽습니다.
    - 재귀 호출 횟수가 매우 많을 때 스택 오버플로우발생 가능성예
- 방법 3. 무차별 사용
  - 간단하고 이해하기 쉽습니다.
  - 주어진 두 수가 클 경우 유클리드 호제법보다 비효율적

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이 아닌 경우에 반복
        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. 브루트포스

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

프로그래머스

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

1. 문제

2. 문제 해결 로직

3. 코드 구현

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

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

3-3. 브루트포스

인기글