최소공배수(lcm), 최대공약수(gcd)

티스토리 뷰

PS/공부

최소공배수(lcm), 최대공약수(gcd)

시르베어 2024. 5. 1. 20:10

매번 최소공배수 / 최대공약수 풀때마다 구하는 방식을 간단히 찾아보고 문제를 풀고 넘어가다 보니 머리속에 남지 않아서 이번 기회에 정리를 하고자 한다.

공배수와 공약수의 개념은 간단하다 공통적으로 가지는 배수와 약수를 뜻한다

3과 4의 공배수는 12, 24, 36 ... 이다

24와 36의 공약수는 1, 2, 3, 4, 6, 12 이다

이때 각 12는 3과 4의 최소공배수 이며, 24와 36의 최대공약수이다

num1 과 num2라는 입력이 들어올 때 처음 접근했던 방식은 간단했다

최소 공배수의 경우 큰 수를 찾아 1부터 하나씩 곱해서 작은수를 나누었을때 나머지가 처음으로 0인 수를 찾았다

func f(_ num1: Int, _ num2: Int) -> Int {
    let maxN: Int = max(num1, num2)
    let minN: Int = min(num1, num2)

    for idx in 1... {
        if (maxN * idx) % minN == 0 {
            return maxN * idx
        }
    }
    return -1
}

이 방법의 단점은 당연히 반복문을 써서 불필요한 계산 과정이 생긴다는 것이다

또한 최소 공배수가 num1 * num2인 경우에 시간을 많이 쓰게 된다

최대공약수의 경우는 작은 수를 작은 수 부터 1까지 나누고 이때 나누어 떨어진 수로 큰 수를 나누었을때 나머지가 처음으로 0인 수를 찾았다

func f(_ num1: Int, _ num2: Int) -> Int {
    let maxN: Int = max(num1, num2)
    let minN: Int = min(num1, num2)
    var gcd: Int = -1
    for idx in (1...minN).reversed() {
        if minN % idx == 0 && maxN % idx == 0{
            gcd = idx
        }
    }

    return gcd
}

이 또한 반복문을 사용해서 불필요한 계산 과정이 들어가고 최대 공약수가 1인 경우가 되면 시간 소요가 많이 들어간다

최소 공배수와 최대 공약수에 대한 내용은 위키백과에서 확인할 수 있다

또한 해당 글에서는 최소 공배수와 최대 공약수를 어떻게 구할 것인가? 라기 보다 알고리즘 문제를 푸는데 해당 내용이 기억나지 않아 정리 하면서 방법을 기억하고자 하여 작성한 것이므로 상세한 설명은 넘어간다

최대 공약수

최대 공약수의 경우엔 유클리드 호제법을 사용하는데 유클리드 호제법을 간단히 설명하면 특정 두 수(큰 수, 작은 수)를 나누어 나머지가 0인 경우를 찾는것이다

예시로 20과 12의 최대 공약수를 구하면

1) 20 % 12 = 8

2) 12 % 8 = 4

3) 8 % 4 = 0

따라서 4는 20과 12의 최대 공약수가 된다

1) 에서 큰 수(20)을 작은 수(12)로 나누었을때 나머지가 8이므로

2) 에서 큰 수가 12가 되고 작은 수가 8이 된다. 이런 식으로 나머지가 0이 될 때 까지 진행하면 되는데

3) 에서 큰 수(8)은 작은 수(4) 로 나누어 떨어져 나머지가 0이 되므로 계산은 끝나고 최대 공약수는 4가 된다

func gcd(_ num1: Int, _ num2: Int) -> Int { //num1은 큰 수, num2는 작은 수
    if num1 % num2 == 0 { return num2 }
    return gcd(num2, num1%num2)
}
func gcd(_ num1: Int, _ num2: Int) -> Int { //num1은 큰 수, num2는 작은 수
    var num1: Int = num1
    var num2: Int = num2
    while num1 % num2 != 0 {
    	let temp = num1 % num2
        num1 = num2
        num2 = temp
    }
    return num2
}