[알고리즘] 유클리드 호제법, 유클리드 알고리즘

유클리드 호제법

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.

여기서 호제법이란?

 

호제법은 2개의 숫자가 상대방의 수로 나누어서 원하는 수를 얻는 알고리즘을 뜻한다.

 

a가 b보다 클때 a를 b나눈 것의 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

 

(a > b)
r = a % b
(a, b) = (b, r)

 

만약 여기서 b를 r로 나눈 값의 나머지가 0 이면 a와 b의 최대공약수는 r인 것이고, 0이 아닌 경우

b를 r 로 나눈것의 나머지(r') 를 b 자리에 두고 a자리에는 b를 두고 다시 계산한다.

(b, r) = (r, r') 
...

이 과정을 N 회 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다.

 

[백준 2609번] 최대공약수와 최소공배수

https://www.acmicpc.net/problem/2609

 

💡구상

최대공약수는 유클리드 호제법을 사용한다 하면,

최소공배수는 어떻게 해야할까?

최대공약수와 최소공배수의 연관관계에 대해 고민해보자.

 

유클리드 호제법

A = 24, B = 18
R = 24 % 18 = 6
(A, B) = (B, R)
(24, 18) = (18, 6) = (6, 0) = 6

 

유클리드 호제법으로 A와 B의 최대공약수를 구할 수 있었다.

 

최대공약수를 이용해 최소공배수를 구하는 법은

최대공약수 = G
최소공배수 L = G * a * b
A = G * a
B = G * b
A * B = G * a * b * G
(L = G * a * b 대입)
A * B = L * G
G = (A * B)/L

 

위의 식에 구한 최대공약수와 A, B 를 대입하면

G = (24 * 18) / 6 
G = 432 / 6
G = 72

 

이것으로 알고리즘을 해결하기 위한 식은 모두 갖춰졌다.

 

🔍 코드

let [A, B] = require("fs").readFileSync("./input.txt", "utf-8").trim().split(" ").map(Number);
let [a, b] = [A, B];
if (A < B) [A, B] = [B, A];
if (A !== B) {
  while (A % B !== 0) {
    let R = A % B;
    if (R !== 0) [A, B] = [B, R];
  }
}
console.log(`${B}\n${(a * b) / B}`);

 

❗️주의할점

주어진 조건을 보면 

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

 

라고 되어 있다. 이 조건에서 알 수 있는 것은 10,000 이하의 수 이면서 자연수이기에 양수만 주어짐을 알 수 있다.

하지만, 두 개의 자연수가 주어질때 A,B 를 기준으로 어떤 쪽이 더 큰값이 올지 알 수 없고, A와 B가 같은 경우 또한 고려해야 한다.

 

그것을 처리하기 위해서 

// ...
if (A < B) [A, B] = [B, A];
if (A !== B) {
// ...

 

조건문을 추가하여 어떠한 경우에도 A에는 B보다 큰 값이 위치한다.

 

🔥 배운점

처음 이 문제를 접하고는 단순하다 생각하고, 일반적인

최대공약수를 구하는 방법으로 접근해 코드로 구현을 하려니 막막했다.

힌트를 얻기 위해 아래 어떤 알고리즘이 사용된건지를 찾아보니 유클리드 호제법을 사용한 문제임을 알 수 있었는데,

처음 들어본 알고리즘이기 때문에 학습을 진행했다. 

어렵지 않은 문제로 분류되어 있었고, 정답비율도 절반 이상인 터라 만만하게 접근했다가 무지함에

스스로를 되돌아보는 시간이었다.