Algorithm) 유클리드 호제법

https://school.programmers.co.kr/learn/courses/30/lessons/12953#

최대공약수와 관련되 문제를 풀고 '다른 사람의 풀이'를 보다가 알게 된 내용이다. 아예 모르는 내용이었기 때문에 정리해보려고 한다.

유클리드 호제법

정의) 자연수 a,b (a> b)가 있을때 a를 b로 나눈 나머지를 r이라 할때 a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.

이용) 따라서 b를 r로 또 나누고 나온 r'를 이용하여 r을 r'로 나누는 과정을 반복하여 나머지가 0이 나올때 나눈 수가 최대공약수가 된다.

증명해보자!

따라서 r 또한 b와 공약수 G를 가지며 (A-qB)와 B가 서로수 관계임을 증명하면 된다.

귀류법 이용 (한 명제의 역이 거짓임을 증명해 그 명제의 참을 증명하는 방법)

역 가정: (A-qB)와 B가 서로수가 아니다.

A와 B가 공약수 t를 갖으며 서로수 관계가 아니게 된다
-> 위 명제(A,B는 서로수이다)에 反
역설적인 결과가 나왔으므로 (A-qB)와 B는 서로수일 수 밖에 없다.

유클리드 호제법을 이용하여 알고리즘 풀기

나머지가 0이 되어야 함을 이용하여 빠르게 최대공약수 찾기

	fun maxCommonDivisor(a: Int, b: Int): Int {
        var x = a
        var y = b

        while (y != 0) {
            val temp = y
            y = x % y
            x = temp
        }
        return x
    }

따라서 두 수의 최소공배수는 쉽게 구할 수 있다.

  fun minCommonMultiple(a: Int, b: Int): Int
            = a * b / maxCommonDivisor(a, b)

그러면 solution함수는

	fun solution(arr: IntArray): Int {
        var answer = 1
        
        arr.forEach{
            answer = minCommonMultiple(answer, it)
        }
        
        return answer
    }

기존에 내가 풀었던 방법보다 훨씬 빠르고 간단하다.