백준 알고리즘 2609번(유클리드 알고리즘)

나는 더 간결하고 흡입력있는 코드를 짜기 위해서 알고리즘을 공부하고있다. 알고리즘 문제를 풀고 나서 나보다 코드길이가 더 작은 사람의 코드를 보곤한다. 이번 문제도 문제를 풀고 나서 나보다 코드 길이가 작은 사람의 코드를 보았고 이해가 너무 안 되어서 chat-gpt한테 코드를 해석해달라고 하였다. 알고보니 그 코드는 "유클리드 알고리즘"을 사용하고 있었고 나는 유클리드 알고리즘에 대해 들어본적이 없어서 생소해 이해가 안 되었던 것 이였다. 그래서 처음 푼 코드와 유클리드 알고리즘을 사용하여 푼 코드 총 2개를 사용해서 문제를 풀었다.

---

백준 2609번 문제

문제

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

입력

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

출력

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

문제풀이

문제자체는 정답률이 58퍼센트가 될만큼 어려운 문제는 아니였다. 그래서 코드작성하는데 15분정도 걸렸던거 같다. 

첫번째 코드

String[] inputs = Console.ReadLine().Split();

int num1 = int.Parse(inputs[0]);
int num2 = int.Parse(inputs[1]);

int min = num1 >= num2 ? num2 : num1;

int output1 = int.MinValue;
int output2 = int.MinValue;

for (int i = min; i > 0; i--)
{
    if (num1 % i == 0 && num2 % i == 0)
    {
        output1 = i;
        output2 = (num1 / output1) * (num2 / output1) * output1;
        Console.WriteLine(output1);
        Console.WriteLine(output2);
        break;
    }
}

입력값을 num1과 num2로 나누고 최대공약수를 먼저 구하기 위해 입력값중 작은 수만큼 for문을 반복을 시켰다. 작은 수부터 i가 1씩 작아지고 num1과 num2를 둘다 나누게 된다면 최대공약수가 된다. 최소공배수는 최대공약수와 두 수를 최소공배수로 나눈 값을 곱한 값으로 구했다.

이 문제를 풀고 나는 다른 사람들의 코드 길이를 확인해보았다. 내코드길이는 468B인데 반해 내가 참고한 사람의 코드는 280B밖에 되지 않았다. 그 사람의 코드는 아래에서 확인할 수있다.

https://www.acmicpc.net/source/55182723

로그인

이 코드에서 while 부분이 이해가 되지 않아 챗 지피티에게 해석을 맡겼고 아래의 답변을 내놓았다.

---

Chat-GPT가 대답한 문장

코드의 첫 번째 줄은 콘솔에서 사용자 입력을 읽고 Split() 메서드를 사용하여 두 개의 숫자로 분할한 다음 int.Parse() 메서드를 사용하여 정수 값으로 변환합니다. 이러한 정수 값은 n이라는 정수 배열에 저장됩니다.

코드의 다음 두 줄은 변수 a와 b를 각각 n 배열의 첫 번째 요소와 두 번째 요소로 초기화합니다.

다음 코드 블록은 유클리드 알고리즘을 사용하여 a와 b의 최대 공약수를 찾아 변수 n1에 저장합니다. 알고리즘은 c를 a 값으로 설정하고 a를 b 값으로 설정하고 b를 b로 나눈 나머지 c로 b를 설정합니다. 영. 이 시점에서 a는 a와 b의 원래 값의 최대 공약수를 포함합니다.

코드의 다음 줄은 n2 = n[0] * n[1] / n1 공식을 사용하여 a와 b의 최소 공배수를 계산합니다. 최소 공배수는 'a'와 'b'가 모두 균등하게 나누어지는 가장 작은 배수입니다.

마지막으로, 코드의 마지막 두 줄은 n1 및 n2의 값을 문자열 보간법을 사용하여 정수 형식으로 콘솔에 출력합니다.

---

while 부분을 유클리드 알고리즘이라고 말하길래 유클리드 알고리즘에 대해 찾아보았다.

유클리드 알고리즘에 대해 간단히 말하면 gcd(A,B)와 gcd(B,r)이 같다는 것이다. 이떄 A=qB+r이다. 자세한 설명은 아래 링크에서 포스팅했다.

유클리드 알고리즘 정의

 

나의 코드도 유클리드 알고리즘을 적용하여 바꾸어보았다.

두번째 코드

String[] inputs = Console.ReadLine().Split();

int num1 = int.Parse(inputs[0]);
int num2 = int.Parse(inputs[1]);

int save;

while (num2!=0)
{
    save = num1;
    num1 = num2;
    num2 = save % num2;
}

int output1 = num1;
int output2 = int.Parse(inputs[0]) * int.Parse(inputs[1]) / output1;

Console.WriteLine(output1);
Console.WriteLine(output2);

코드길이는 468B에서 349B까지 줄어들었다. 이미 수학적으로 증명된 명제를 알고리즘으로 사용할 수 있다는 것을 알게되어 수학적 알고리즘을 찾아 공부하는 것도 중요하다고 생각한다.