[Programmers][Java]최대공약수와 최소공배수

728x90

Programmers_Level_1

2023.12.15 - [코딩테스트/프로그래머스] - [Programmers][Java]최대공약수와 최소공배수

2023.12.16 - [코딩테스트/프로그래머스] - [Programmers][Java]같은 숫자는 싫어

2023.12.16 - [코딩테스트/프로그래머스] - [Programmers][Java]3진법 뒤집기

2023.12.17 - [코딩테스트/프로그래머스] - [Programmers][Java]예산

2023.12.18 - [코딩테스트/프로그래머스] - [Programmers][Java]이상한 문자 만들기

2023.12.18 - [코딩테스트/프로그래머스] - [Programmers][Java]크기가 작은 부분문자열

2023.12.21 - [코딩테스트/프로그래머스] - [Programmers][Java]삼총사

🏁 Programmers_Level_1
📖 최대공약수와 최소공배수

❔ 문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.
배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.
예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

🚫 제한 사항

⁕ 두 수는 1이상 1000000 이하의 자연수입니다.

✅ 입출력 예

n	m	result
3	12	[3, 12]
2	5	[1, 10]

📃 입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

💻 내 작성 코드

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        answer[0] = gcd(n,m);
        answer[1] = n * m / answer[0];
        
        return answer;
    }
    
    public int gcd(int n, int m) {
        while(m != 0) {
            int r = n % m;
            n = m;
            m = r;
        }
        return n;
    }
}

저는 유클리드 호제법을 이용하여 최대공약수를 구했고,
n * m / 최대공약수를 이용하여 최소공배수를 구했습니다.

유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘입니다. 이 방법은 고대 그리스 수학자 유클리드가 '원론'이라는 책에서 처음 소개했습니다.

유클리드 호제법의 기본 아이디어는 다음과 같습니다:
두 수 n, m (n > m)가 있을 때, n을 m로 나눈 나머지를 r이라 하면, n와 m의 최대공약수는 m와 r의 최대공약수와 같다는 것입니다. 이 성질을 이용하여 m을 n에 대한 나머지로 계속 대체하면서, 나머지가 0이 될 때까지 반복합니다. 나머지가 0이 되었을 때의 m이 n과 m의 최대공약수(GCD)가 됩니다.

예를 들어, 48과 18의 최대공약수를 구한다고 가정해 봅시다:

48 ÷ 18 = 2...12 (나머지가 12)
18 ÷ 12 = 1...6 (나머지가 6)
12 ÷ 6 = 2...0 (나머지가 0)
따라서, 48과 18의 최대 공약수는 6입니다. 이처럼 유클리드 호제법은 반복적이고 간단한 계산을 통해 빠르게 최대공약수를 구할 수 있는 장점이 있습니다.

두 수의 최소공배수(LCM)를 구하는 가장 간단한 방법은 두 수의 곱을 그들의 최대공약수(GCD)로 나누는 것입니다.

이는 두 수 n과 m의 최소공배수와 최대공약수가 다음과 같은 관계가 있기 때문입니다:
n * m = GCD(n, m) * LCM(n, m)
따라서, LCM(n, m) = (n * m) / GCD(n, m)

위에서 언급한 예시인 48과 18을 가지고 계산해 보면:
48과 18의 GCD는 6이었습니다.
따라서, 48과 18의 LCM은 (48 * 18) / 6 = 144입니다.

즉, 48과 18의 최소공배수는 144입니다. 이처럼 최대공약수를 먼저 구한 후에 이를 이용해 최소공배수를 구하면 간단하게 문제를 해결할 수 있습니다.

💻 다른 사람의 풀이

import java.util.Arrays;

class TryHelloWorld {
      public int[] gcdlcm(int a, int b) {
        int[] answer = new int[2];

        answer[0] = gcd(a,b);
        answer[1] = (a*b)/answer[0];
        
        return answer;
    }

   public static int gcd(int p, int q){
       if (q == 0) return p;
       return gcd(q, p%q);
   }

다른 분들 중 재귀함수를 사용하여 풀어낸 코드가 있었습니다.

두 수의 최대공약수(GCD)와 최소공배수(LCM)를 각각 구하는 gcdlcm 함수와 재귀를 이용한 gcd 함수가 잘 구현되어 있습니다.

gcd 함수에서는 유클리드 호제법을 재귀적으로 구현했습니다. 만약 두 번째 인자인 q가 0이라면, 첫 번째 인자인 p가 최대공약수가 됩니다. 그렇지 않다면, gcd 함수를 다시 호출하되, 이번에는 q와 p를 q로 나눈 나머지를 인자로 넘깁니다. 이 과정을 반복하면 결국 최대공약수를 구할 수 있습니다.

gcdlcm 함수에서는 먼저 gcd 함수를 이용해 최대공약수를 구하고, 이를 이용해 최소공배수를 구합니다. 그리고 이 두 값을 배열에 담아 반환합니다.

📒 배운 점

처음에는 최대공약수와 최소공배수를 구하는 방식이 굉장히 어렵게 느껴졌습니다. 그 이유는 그냥 공식 자체가 잘 기억나지 않았기 때문입니다. 하지만 이해하려고 노력하면서, 이 과정이 수학적 개념을 코드로 변환하는 연습이라는 것을 깨달았습니다.

최대공약수와 최소공배수의 개념 이해: 두 수의 공통된 약수 중 가장 큰 수가 '최대공약수', 공통된 배수 중 가장 작은 수가 '최소공배수'임을 이해하는 것부터 시작했습니다.
유클리드 호제법의 이해: 유클리드 호제법은 두 수의 최대공약수를 찾는 가장 효율적인 방법입니다. 큰 수를 작은 수로 나누고, 그 나머지를 다시 작은 수로 나누는 과정을 반복합니다. 이 과정을 통해 '최대공약수'를 찾을 수 있음을 알게 되었습니다.
최소공배수의 계산: 두 수의 최소공배수는 두 수의 곱을 그들의 최대공약수로 나눈 값입니다. 이 공식을 이해하기 위해선 두 수의 곱이 '최대공약수'와 '최소공배수'의 곱과 같다는 사실을 알아야 했습니다.
코드로의 변환: 이제 이해한 개념을 바탕으로 코드를 작성했습니다. 유클리드 호제법을 구현하고, 그 결과를 이용하여 최소공배수를 구했습니다.

이 과정을 통해 수학적 개념을 코드로 변환하는 연습을 하게 되었고, 이는 저에게 새로운 문제나 개념에 대처하는 능력을 키우는 데 큰 도움이 될 것이라고 느꼈습니다. 이런 경험을 통해, 어려운 문제에 부딪혔을 때도 포기하지 않고 문제를 이해하려 노력하는 태도의 중요성을 깨달았습니다.