[ 수학 ] 백준 2609 최대공약수와 최소공배수, Kotlin, 유클리드 알고리즘

문제 링크

2609번: 최대공약수와 최소공배수

 

💡문제 분석 요약

• 두 자연수의 최대 공약수(GCD)와 최소 공배수(LCM)을 구해야한다. 
  • 최대 공약수는 두수를 나머지 없이 나누는 가장 큰수를 의미한다.
  • 최소 공배수는 두 수로 균등하게 나누어지는 가장 작은 수를 의미한다.

 

💡알고리즘 설계

• GCD: a와 b의 GCD를 찾기위해 *유클리드 알고리즘을 사용한다. 
• LCM: GCD를 찾으면, 공식(LCM = (a * b) / a와 b의 GCD)을 활용하여 계산한다.

 

💡코드

import java.util.*

fun gcd(a: Int, b: Int): Int {
    return if (b == 0) a else gcd(b, a % b)
}

fun lcm(a: Int, b: Int): Int {
    return a * b / gcd(a, b)
}

fun main() {
    val scanner = Scanner(System.`in`)
    val a = scanner.nextInt()
    val b = scanner.nextInt()

    println(gcd(a, b))
    println(lcm(a, b))
}

 

 

💡시간복잡도

• GCD 계산: 유클리드 알고리즘의 시간 복잡도는 O(log min(a,b) 이다.
• LCM 계산: LCM 계산에 GCD를 사용하므로, 복잡도는 GCD의 영향을 받아, LCM의 시간복잡도는 O(log min(a,b)) 가 된다.

 

따라서 시간복잡도는 O(log min(a,b)가 된다.

 

💡 느낀점 or 기억할정보

• GCD와 LCM의 관계를 이해하고 있어야 하며, 관련된 개념또한 알고 있어야 한다. 
• GCD를 계산하는 효과적인 알고리즘인 유클리드 알고리즘을 인지하고 있어야 한다.