최대공약수와 최소공배수

나의 풀이

// 최대공약수 구하기
function cal_gcd(x, y) {
  return x % y === 0 ? y : cal_gcd(y, x % y);
}

function solution(n, m) {
  const gcd = cal_gcd(n, m);
  return [gcd, (n * m) / gcd];
}

1. 유클리드 호제법을 사용하여 일단 최대공약수를 구해준다.
2. n과 m을 곱한 숫자에 최대공약수를 나누어 최소공배수를 구해준다.

유클리드 호제법

유클리드 호제법(- 互除法, Euclidean Algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘의 하나이다.

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.

유클리드 호제법의 알고리즘은 다음과 같다.

1. 입력으로 두 수 m,n(m>n)이 들어온다.
2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
3. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

여기에서 m>n이라는 조건이 붙어있지만, 내가 작성한 코드에는 그러한 조건이 붙어있지 않다. 왜냐하면 어떤 수를 자신보다 더 큰 수로 나누게 되면 몫은 0, 나머지는 자기 자신이 되는 것을 활용하였기 때문이다.

위 문제를 예로 들자면 (m>n)이라는 조건에 따라 m은 12, n은 3이 되어야 한다. 하지만 m이 3, n이 12가 되더라도 내가 작성한 코드는 정상적으로 작동한다. 3을 12로 나눈 나머지의 값은 3이 되고, 이는 0이 아니기 때문에 알고리즘 4번에 의하여 두 자리의 숫자를 바꾸어 코드가 다시 진행되기 때문이다.

다른 사람의 풀이

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

처음 이 풀이를 보았을 때에는 이해가 되지 않았다. 내가 그동안 알던 for문은 i가 0부터 배열의 끝까지, i를 증가시켜가면서 순회하는 모습이었는데, for(var ab= a*b;r = a % b;a = b, b = r){}의 모습은 듣도보도 못했었기 때문이다.

혼자 고민하다가 MDN을 보고 for의 구문을 제대로 파악할 수 있었다.

for ([initialization]; [condition]; [final-expression])
       statement
       

즉, 위의 풀이에서는 r = a % b부분이 조건식으로 사용되고 있었고, 이것이 0이 나오게 된다면 false이기 때문에 그 다음 평가식인 a = b, b = r이 실행되지 않는다는 것을 이해하게 되었다. 내가 이해한대로 손코딩을 해보았고, 그로 인해 더 자세히 이해할 수 있게 되었다.

오늘의 교훈

• for문의 구문에 대해 다시한번 생각해보게 되었다.
  • initialization: 식 또는 변수 선언
  • condition: 매 반복마다 평가할 식. 평가 결과가 참이라면 statement 실행, 거짓이라면 for 문의 다음 식으로 건너 뜀.
  • final-expression: 반복 후 평가할 식
    • 위 3개의 식은 모두 선택 사항이다.
  • statement: 조건의 평가 결과가 참일 때 실행하는 문. 아무것도 실행하지 않을 수 있다.(이때는 공백문(;) 사용)