11653번 (2강 최적화) 질문이있습니다.

2주만에 통과하는 알고리즘 코딩테스트 (2024년)

최적화 (정수론) - ( 난이도 ⭐️⭐️⭐️⭐️⭐️ , 스킵하셔도 괜찮습니다. )

해결된 질문

작성

173

아래와 같이 완전탐색(?)을 이용해 작성하였는데요, 말씀하신 최적화 방법(약수를 구할때는 해당 수의 제곱근까지만 구해도 약수의 개수와 약수를 구할 수 있다)으로 어떻게 코드를 최적화 할 수 있을지 잘 모르겠습니다.

let input = readLine().map { Int($0)! }!

var answer: [Int] = []
var previous = input

func check(i: Int, divided: Int) -> Bool {
    if divided % i == .zero {
        answer.append(i)
        previous = divided / i
        return true
    } else {
        return false
    }
}

if input == 1 {
    
} else {
    for i in 2...(input) {
        var flag = true

        repeat {
            let check = check(i: i, divided: previous)
            flag = check
        } while flag
    }
    
    answer.compactMap { print(String($0)) }
}

코딩-테스트 알고리즘 swift

답변 2

leedoy7989

질문자



 최적화
 보석값 입력 받기
let gem = readLine().map { Double($0)! }!


//소인수 분해해야함.
var answers: [Int] = []
var previous = Int(gem)
var squreRoot = Int(Double(gem).squareRoot())

func check2(divided: Int, i: Int) -> Bool {
    if divided % i == .zero {
        previous = divided / i
        answers.append(i)
        return true
    } else {
        return false
    }
}
//2,3,4
for i in 2...squreRoot {
    var flag = true
    repeat {
      let result = check2(divided: previous, i: i)
        flag = result
    } while flag
}

if previous != 1 {
    answers.append(previous)
}


answers.sort()
print(answers.count)
print(answers.compactMap { String($0) }.joined(separator: " "))

통과한 답변 공유합니다~

코딩 센세

지식공유자

공유 감사합니다!😄

코딩 센세

지식공유자

질문 감사합니다 :)!!!

저는 아래와 같은 방법으로 최적화를 했습니다 🙂

강의 우측 상단에 보시면 강의자료 다운로드가 가능합니다 !

거기에 제 코드도 있으니 풀어보시고 어려우시면 참고자료로 사용해주세요!

최적화 전 (BOJ https://www.acmicpc.net/problem/11653 )

numbers = int(input())
d = 2
while d <= numbers: 
    if numbers % d == 0: 
        print(d) 
        numbers = numbers / d 
    else: 
        d = d + 1

최적화 후 (BOJ https://www.acmicpc.net/problem/14232 )

number = int(input())

answer = []

for i in range(2, (int(number**0.5) +1)):

    while(number % i == 0):

        answer.append(i)

        number //= i   

if number != 1 :

    answer.append(number)

print(len(answer))

print(*answer)