math_Programmers_N개의 최소공배수 [swift]

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

문제접근

• 매개변수로 Array<Int>, count == n 1<=n<=15가 전달된다. 이 수들의 최소 공배수를 구한다.
• 전달된 Array를 복사하여, 전부 같은지 확인하고, 같지 않다면 가장 작은 원소index를 찾는다.
• 원본의 같은 위치의 element를 해당 index의 원소에 더하고 다시 같은지 확인한다.
• 이를 반복한다.

만들때부터 시간적으로 문제가 있을 것이라 생각하였다.

코드로 소인수 분해를 구현해 볼 까 했지만, 일단 쉬운 방법으로 접근하였다.

오답코드

func solution(_ arr:[Int]) -> Int {
    var sol = arr
    
    while !sol.filter { $0 != sol[0] }.isEmpty {
        guard let target = sol.firstIndex(where: { sol.min() == $0 })
        else { break }
        sol[target] += arr[target]
    }
    return sol.first!
}

예상대로 테스트케이스 두개에서 시간초과가 발생했다.

이론

해결방법은 3가지가 존재한다.

1. 첫 시도인 배수나열법 ( 내 코드로 보아할 떄 O(n^2)급,, gpt는 O(a x b) 란다.
2. 소인수 분해법 ( O(√n)로 구현할 수 있다고 한다.
3. 유클리드 호제법 ( 최적의 알고리즘)

나의 정답코드 - 소인수 분해법

- 전개 과정

• 소인수 분해
• 소인수 중 최대값을 곱하여 답을 반환

func solution(_ arr:[Int]) -> Int {
    var breakdowns = arr.map { breakdown($0) }
    var dic = [Int: Int]()
    
    for nums in breakdowns {
        var _dic = [Int: Int]()
        for num in nums {
            if _dic[num] == nil {
                _dic[num] = 1
            } else {
                _dic[num]! += 1
            }
        }
        for key in _dic.keys {
            if dic[key] == nil {
                dic[key] = _dic[key]
            } else if dic[key]! < _dic[key]! {
                dic[key] = _dic[key]
            }
        }
    }
    // print(breakdowns)
    // print(dic)
    var sol = 1
    for element in dic {
        for _ in 0..<element.value {
            sol = sol * element.key 
        }
    }
    return sol
}

func breakdown(_ target: Int) -> [Int] {
    var sol = [Int]()
    for i in 1...target {
        guard i != 1, target%i == 0 else { continue }
        
        let next = target/i
        sol.append(i)
        let elses = breakdown(next)
        sol.append(contentsOf: elses)
        break
    }
    
    return sol
}

수학적인 소인수 분해법 코드 ( GPT )

제곱근을 이용하여 소인수분해한다.

어렸을 때 배웠던 것 같기도,,,

코드들의 구성이 멋지다 🥹 대단해

import Foundation

// ✅ 소인수 분해 함수 (O(√n))
func primeFactorization(_ n: Int) -> [Int: Int] {
    var num = n
    var factors: [Int: Int] = [:]  // [소수: 승수] 형태의 딕셔너리
    
    // 2부터 √n까지 나누면서 소인수 찾기
    for i in 2...Int(Double(n).squareRoot()) {
        while num % i == 0 {
            factors[i, default: 0] += 1
            num /= i
        }
    }
    
    // 마지막에 남은 수가 소수라면 추가
    if num > 1 {
        factors[num, default: 0] += 1
    }
    
    return factors
}

// ✅ 여러 숫자의 최소공배수 (LCM) 구하기
func lcmOfNumbers(_ numbers: [Int]) -> Int {
    var lcmFactors: [Int: Int] = [:]  // [소수: 최댓값 승수]

    for num in numbers {
        let factors = primeFactorization(num)
        for (prime, exponent) in factors {
            lcmFactors[prime] = max(lcmFactors[prime, default: 0], exponent)
        }
    }
    
    // 최댓값 승수를 사용하여 최소공배수 계산
    return lcmFactors.reduce(1) { result, pair in
        let (prime, exponent) = pair
        return result * Int(pow(Double(prime), Double(exponent)))
    }
}

// ✅ 여러 숫자의 최대공약수 (GCD) 구하기
func gcdOfNumbers(_ numbers: [Int]) -> Int {
    var gcdFactors: [Int: Int] = [:]  // [소수: 최솟값 승수]
    
    // 첫 번째 숫자의 소인수 분해 결과를 기준으로 설정
    gcdFactors = primeFactorization(numbers[0])

    // 나머지 숫자들과 비교하며 최솟값을 찾음
    for num in numbers.dropFirst() {
        let factors = primeFactorization(num)
        for prime in gcdFactors.keys {
            if let exponent = factors[prime] {
                gcdFactors[prime] = min(gcdFactors[prime]!, exponent)
            } else {
                gcdFactors[prime] = 0  // 공통되지 않으면 제거
            }
        }
    }

    // 최솟값 승수를 사용하여 최대공약수 계산
    return gcdFactors.reduce(1) { result, pair in
        let (prime, exponent) = pair
        return result * Int(pow(Double(prime), Double(exponent)))
    }
}

// ✅ 테스트 실행
let numbers = [12, 18, 24]
print("LCM: \(lcmOfNumbers(numbers))")  // 출력: 72
print("GCD: \(gcdOfNumbers(numbers))")  // 출력: 6

 

모범적인 유클리드 호제법

이거 외워야겠다...

func solution(_ arr:[Int]) -> Int {
    guard arr.count > 2 else { return arr.first!}
    
    return arr.reduce(1, { lcm($0, $1) })
}
func lcm(_ a: Int, _ b: Int) -> Int {
    return a * b / gcd(a,b)
}

func gcd(_ a: Int, _ b: Int) -> Int {
    return b == 0 ? a : gcd(b, a%b)
}

 

유클리드 호제법에 대하여

유클리드 호제법은 두 수의 최대공약수(GCD)는 큰 수에서 작은 수를 빼도 변하지 않는다는 성질을 이용합니다.

즉,

 

GCD(a, b) = GCD(a - b, b)

 

이 성질을 반복 적용하면 나눗셈의 나머지로 GCD를 구할 수 있습니다.

우리는 어떤 수 a, b(a > b)에 대해

• d가 a와 b의 공약수라고 가정합니다. 즉,

• a = d × x

• b = d × y

• 여기서 x, y는 정수입니다.

 

그런데, a - b도 d의 배수인지 확인해봅시다.

큰 수 a를 작은 수 b로 나눈 나머지를 r이라고 하겠습니다.

a = k × b + r  (여기서 k는 몫, r은 나머지)

a = d × x
b = d × y

r = a - k × b = d × x - k × (d × y) = d × (x - k × y)

즉, r도 d의 배수임을 알 수 있습니다.

➡ 결론:

 

a, b의 최대공약수 GCD(a, b)는 b와 r의 최대공약수 GCD(b, r)과 같다.

 

즉,

 

GCD(a, b) = GCD(b, a % b)

(나머지가 0이 될 때까지 계속 나누면 GCD를 구할 수 있다!)

 

GCD(a, b) = GCD(b, a % b) 식은 a < b여도 항상 작동합니다.

이제 a < b인 경우를 생각해 봅시다.

예를 들어 GCD(12, 48)을 구한다고 가정하면:

12 % 48 = 12  (왜냐하면 12가 48보다 작아서 나머지가 그대로 12)
즉, GCD(12, 48) = GCD(48, 12)