[ Algorithm ] Baekjoon_2609 : Kotlin

안녕하세요 공공돌🧸 입니다 !!

오늘은 백준 알고리즘의 2609 : 최대공약수와 최소공배수 를 풀어보고 리뷰를 해보려 합니다.

먼저 문제를 풀기 전 저의 목표는 알고리즘 문제 풀이도 있지만, 기능들을 나누어 구현하는것을 목표로 삼았습니다.

 

문제는 아래 링크를 참고해주세요.

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

---

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

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

6
72

---

기능 정리

✅ 두 개의 자연수를 입력받는다.

✅ 최대 공약수를 계산한다

✅ 최소 공배수를 계산한다.

 

---

핵심

이번 문제의 핵심은 최대 공약수와 최소 공배수를 어떻게 계산하는지가 핵심이라고 생각합니다.

 

저는 유클리드 호제법을 활용하여 문제를 풀었습니다.

아래와 같이 유클리드 호제법을 활용하면 간단하게 최대공약수와 최소공배수를 구할 수 있습니다.

 

✏️ 유클리드 호제법이란?

유클리드 호제법(Euclidean algorithm)은 두 개의 정수(또는 자연수)의 최대공약수를 구하는 데 사용되는 수학적인 알고리즘입니다.

 

유클리드 호제법을 활용하여 최대 공약수(GCD, Greatest Common Divisor)와 최소 공배수(LCM, Least Common Multiple)를 구하는 방법은 아래와 같습니다.

---

최대공약수(GCD) 구하는 방법

유클리드 호제법 사용
주어진 두 정수 a와 b에 대해 유클리드 호제법을 사용하여 최대공약수(GCD)를 구합니다.

유클리드 호제법의 단계

1. a를 b로 나눕니다.
2. 나머지를 구합니다. 나머지를 r이라고 합니다.
3. r이 0이면, b가 최대공약수(GCD)입니다.
4. r이 0이 아니면, a를 b로, b를 r로 대체하고 1단계로 돌아갑니다.

 

예시

a = 24, b = 18로 시작하면 다음과 같이 계산됩니다.

24 ÷ 18 = 1 (나머지 6)
18 ÷ 6 = 3 (나머지 0)
따라서, GCD(24, 18) = 3입니다.

---

최소공배수(LCM) 구하는 방법

두 정수의 곱 사용

주어진 두 정수 a와 b에 대해 최소공배수(LCM)를 구하는 방법은 다음과 같습니다.
먼저, 두 정수 a와 b의 최대공약수(GCD)를 구합니다. 이전 단계에서 설명한 유클리드 호제법을 사용하여 GCD를 구할 수 있습니다.
그런 다음, 다음 공식을 사용하여 LCM을 계산합니다

 

LCM(a, b) = (a * b) / GCD(a, b)

 

예시
a = 24, b = 18, GCD(24, 18) = 3으로 계산했다면,
LCM(24, 18) = (24 * 18) / 6 = 144입니다.

 

---

코드 구현

main

fun main() {
    val input = readln().split(" ")
    val a = input[0]
    val b = input[1]
    val gcd = greatestCommonDivisor(a.toLong(), b.toLong())
    val lcm = leastCommonMultiple(a.toLong(), b.toLong(), gcd)
    println(gcd)
    println(lcm)
}

 

입력값을 공백을 기준으로 리스트로 변환합니다.

첫번째 값은 a, 두번째 값은 b 변수에 넣습니다.

gcd의 값과 lcm의 값을 반환받습니다.

gcd와 lcm을 출력합니다.

 

✏️ 왜 Int형이 아닌 Long 형으로 계산할까?

• 데이터의 범위를 다룰 때 : Long은 더 큰 범위의 정수 값을 나타낼 수 있습니다. 때때로 최대공약수(GCD)를 구할 때 정수 값이 아주 크거나, Int 범위를 초과할 수 있습니다. 이런 경우 Long을 사용하여 더 큰 범위의 데이터를 다룰 수 있습니다.
  
  
• 호출 시 다양한 데이터 타입을 다룰 수 있도록 하기 위함 : Long을 사용하면 두 정수가 Int 범위를 벗어나더라도 함수를 호출할 수 있습니다. 다시 말해, Int뿐만 아니라 Long 타입의 정수도 처리할 수 있습니다. 이렇게 함으로써 함수는 더 일반적이고 유연하게 사용할 수 있습니다.

---

greatestCommonDivisor

private fun greatestCommonDivisor(a: Long, b: Long): Long {
    if (a % b == 0L) return b
    return greatestCommonDivisor(b, a % b)
}

 

재귀 함수를 통해 a와 b를 나눈 나머지가 0L와 같다면 b를 반환합니다.

이때 0L는 long 타입의 0을 말합니다.

만약 0L과 같지 않다면 나머지가 0이 될 때까지 반복합니다.

---

leastCommonMultiple

private fun leastCommonMultiple(a: Long, b: Long, gcd: Long): Long {
    return (a * b) / gcd
}

 

a와 b를 곱한 값에 앞에서 구한 gcd를 나누어 값을 반환합니다.

---

최종 코드 구현

fun main() {
    val input = readln().split(" ")
    val n = input[0]
    val m = input[1]
    val gcd = greatestCommonDivisor(n.toLong(), m.toLong())
    val lcm = leastCommonMultiple(n.toLong(), m.toLong(), gcd)
    println(gcd)
    println(lcm)
}

private fun greatestCommonDivisor(a: Long, b: Long): Long {
    if (a % b == 0L) return b
    return greatestCommonDivisor(b, a % b)
}

private fun leastCommonMultiple(n: Long, m: Long, gcd: Long): Long {
    return (n * m) / gcd
}

---

결과

---

공부하는 공돌이, 공공돌입니다🐻

@sheep1sik