[코풀수: 산술] 최대 공약수 (유클리드 호제법)

날짜:
앞의 글에서 소인수 분해 를 이용하여 최대 공약수 를 구하는 알고리즘에 대해 소개하였다. 입력한 두 수를 소인수 분해해서 공통 소인수와 그에 해당하는 최소 지수를 구해야 해서 알고리즘 상으로는 구현이 복잡했다. 최대공약수를 구하는 가장 고전적인 방법인 유클리드 호제법을 활용해 보자. 어떤 알고리즘을 사용하느냐에 따라 코딩이 얼마나 단순해질 수 있는지 확인해 보기 바란다.


유클리드 호제법?


호제법(互除法)이란 두 수가 서로 상대방의 수를 나누어서 원하는 수를 얻는 것이다. 예를 들어 75와 45의 최대 공약수를 구해보자.


따라서 위의 결과에 따라 75와 45의 최대 공약수는 15이다.

최대 공약수 (유클리드 호제법)

N:
M:

답:

유클리드 호제법 일반화


두 자연수 N과 M에 대해 일반화를 시켜보자.


위의 수식을 자세히 보면 나머지 0이 될 때까지 나머지로 계속 나눠가는 작업을 반복한다. 컴퓨터로는 반복을 쉽게 할 수 있다. 특히 재귀함수(함수내에서 자신을 또 호출하는 것)라는 것을 활용하면 코드를 매우 단순화 시킬 수 있다.

<!DOCTYPE html>
<html>
<title>최대 공약수 (유클리드 호제법)</title>
<body>

<h4>최대 공약수 (유클리드 호제법)</h4>

<form>
  N: <input type="text" id="N" value="12"><br>
  M: <input type="text" id="M" value="18"><br>
  <input type="button" id="find_gcd" value="최대공약수 구하기"><br>
</form>

<p id="result">답: </p>

<script>
    document.getElementById("find_gcd").addEventListener("click", calc);
    
    function calc() {
        // 입력된 문자열을 숫자로 바꾸고, 자연수인지를 체크하기
        N = Number(document.getElementById("N").value);
        if (isNaN(N) || N < 1 || N % 1 != 0) {
            document.getElementById("result").innerHTML = "자연수를 입력하세요.";
            return;
        }
        M = Number(document.getElementById("M").value);
        if (isNaN(M) || M < 1 || M % 1 != 0) {
            document.getElementById("result").innerHTML = "자연수를 입력하세요.";
            return;
        }
        
        var gcd = getGCD(N, M);
        document.getElementById("result").innerHTML = N + "과 " + M + "의 최대공약수는 " + gcd + "입니다.";
    }

    function getGCD(n, m) {
        return n%m ? getGCD(m, n%m) : m;
    }
</script>

</body>
</html>

[코드설명] n%m ? getGCD(m, n%m) : m;
n%m에서 %는 모듈라(Modular) 연산자로 n을 m을 나눌 때 나머지를 반환한다. 따라서 나머지가 0이 아니면(참, javascript에서는 0이 아니면 참임), 재귀 호출을 하고, 0이면 m을 반환한다(답이 m이 된다).
재귀 호출을 할때는 n -> m이 되고 m -> n%m (나머지)로 바꿔준다.

댓글

댓글 쓰기