[BOJ]2609 최대공약수와 최소공배수 (kotlin)

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

요즘 취준을 하다보니 여러모로 코테가 자꾸 발목을 잡아서 본격적으로 코테준비를 하고있다.🥲

이번에 푼 문제는 ‘최대공약수와 최소공배수’를 구하는 문제였다.

처음에는 아래와 같은 방법으로 최대공약수와 최소공배수를 구하였다.

• 최대 공약수

  입력된 두 수 중 작은 수(n2)부터 2까지 하나씩 확인하며 두 수 의 나머지가 0이되게 하는 가장 큰 수를 찾는다.

  이 경우 시간복잡도는 O(n)이다.

    fun getGCD(n1:Int,n2:Int):Int{
        val min=min(n1,n2)
        for(i in min downTo 2){
            if(n1%i==0 && n2%i==0)return i
        }
        return 1
    }
  

  🤔 n2→2까지 줄어드는 방향으로 반복시킨 이유

  반복 횟수를 최소화 하기 위해서이다.2→n2까지 증가 되는 방향으로 반복하는 경우 공약수를 찾아도 그게 최대 공약수인지 모르므로 결국 끝까지 반복 해야 한다!

• 최소공배수

  입력된 두 수를 곱한 후 최대공약수로 나눈 결과가 최소공배수이다!

    fun getLCM(n1:Int,n2:Int,gcd:Int= getGCD(n1,n2)):Int{
        val mul=n1*n2
        return mul/gcd
    }
  

🚀Advanced

이 문제의 경우는 최대공약수를 구하는 방법에서 개선의 여지가 있었다.

이와 관련된 유명한 알고리즘인 ‘유클리드 호제법’을 사용하는것이다!

유클리드 호제법(Euclidean algorithm) 이란?

[가정]

• n1>n2
• r=n1%n2

[정의]

• r , n2의 최대공약수는 n1 , n2의 최대공약수와 같다.
• 수식으로 쓴다면 $(a,b)=(b,r)$

이렇게 말로 설명하는것이 이해가 잘 안된다면 위키백과에 올라온 그림을 보는것도 도움이 된다!

https://ko.wikipedia.org/wiki/유클리드_호제법

[알고리즘]

1. 입력된 두 수의 대소를 비교 (큰수 : big, 작은수 :small)
2. r=big%small
3. (r==0) small이 최대 공약수!
4. (r≠0) big=small, small=r을 대입한 후 2번부터 반복!

→ 이경우 시간 복잡도는 O(log n)이다!

fun getGCDwithEuclidean(n1:Int,n2:Int):Int{
    var big=max(n1,n2)
    var small=min(n1,n2)
    var r=big%small
    while(r!=0){
        big=small
        small=r
        r=big%small
    }
    return small
}

위와 같이 코드를 바꾸어 아래와 같은 결과를 얻을 수 있었다.

• 실행시간 132ms→128ms로 5.3% 감소