[ 알고리즘 / kotlin ] 최대공약수 구하기 - 유클리드 호제법

안녕하세요 gyub(귭)입니다 ㅎㅎㅎ

 

이번엔 코틀린으로 최대 공약수 구하는 코드를 작성해보려고 합니다.

최대 공약수를 구하는 방법에는 유클리드 호제법( 유클리드 알고리즘)이라는 좋은 방법이 있습니다!!

 

그래서 먼저 유클리드 호제법에 대해서 설명하려고합니다. ( 코드만 궁금하신 분은 밑으로 쭉 내려가세여~~)

위키 백과에 보면

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.  2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

라고 합니다 ㅎ ( 전 처음에 잘 이해가 안 갔어요-__-)

 

이에 좀 더 쉬운 접근 위해 예시를 들며 설명을 할게요

a와 b를 각각 12과 8이라고 하겠습니다.

if( a>b)

a%b는 4가 되겠져 따라서 r= 4가 됩니다

a와 b의 최대공약수는 b와 r의 최대공약수와 같다고 합니다. 이를 이용해보면

b를 r로 나눈 나머지 r` = 4가 되고 b와 r의 최대공약수는 r과 r`의 최대공약수와 같겠죠?!

그러다 반복하면 ( 위 경우엔 r`이 나온 순간 바로 끝나지만 ) 나머지가 0이 되는 날(?)이 옵니다!!

그 때의 나누는 수가 a와 b의 최대공약수가 됩니다

 

자 이제 코틀린 코드로 작성해볼게요!

fun gcd(a: Int, b: Int): Int {
    var maximum = max(a, b)
    var minimum = min(a, b)

    if (minimum == 0) {
        return max(a, b)
    } else {
        return gcd(minimum, maximum % minimum)
    }
}

재귀함수로 작성했습니다!

maximum과 minimum은 매개변수가 랜덤으로 주어질 때를 대비해 작성한것이므로
하드코딩으로 값을 넣어주실 분들은 굳이 안 쓰셔도 돼요!!

 

 

이렇게 최대공약수 구하는 법을 코틀린으로 간단하게 구현해봤습니다~~~~~

 

봐주셔서 감사합니다!
질문이나 수정되어야 할 부분이 있다아면 댓글로 남겨주세요!