#11653 소인수분해 문제(최적화 관련)

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

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

해결된 질문

작성

369

아래와 같이 코드를 작성하였는데 답은 맞췄지만 강의에서 말씀하신 제곱근 아이디어가 반영되어있지 않습니다.

아래 코드를 더 최적화 할 수 있는 아이디어가 있나요?

#11653 소인수분해
N = int(input())
divide = True

while(divide):
    for i in range(2, N+1):
        if N % i == 0: 
            print(i)
            N = N//i
            break
    if N == 1 : 
        divide = False

python 코딩-테스트 알고리즘

답변 2

코딩 센세

지식공유자

답변이 늦어서 죄송합니다! ( 요즘 새 회사에 적응하느라 자꾸 놓치게 되네요 ㅠㅠ... 다롱이님 질문 많이 해주셔서 고마워요 )

소인수분해 문제에서 추가로 최적화는 필요 없어 보입니다 🙂

이 다음 문제로 보석 도둑 문제를 풀면서 제곱근 아이디어를 적용해 보시면 좋을 것 같습니다!

https://www.acmicpc.net/problem/14232

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.
다롱이님, 코드 최적화에 대한 질문 감사합니다.

제시해 주신 코드의 경우 모든 수에 대해 2부터 N까지 나눗셈을 시도하기 때문에, N이 매우 클 경우 비효율적일 수 있습니다. 이를 개선하기 위해 제곱근 아이디어를 사용할 수 있습니다. 소인수분해에서 소인수는 N의 제곱근을 넘어가지 않기 때문에, 제곱근까지만 나눗셈을 시도하여 시간 복잡도를 개선할 수 있습니다.

수정하신 코드는 다음과 같을 수 있습니다:

#11653 소인수분해 최적화
N = int(input())
i = 2
while i*i <= N:
    while N % i == 0:
        print(i)
        N //= i
    i += 1
if N > 1:
    print(N)

위 코드에서는 i가 2부터 시작하여 i*i <= N 조건을 만족하는 동안 반복하게 됩니다. 이러한 방식으로, N의 제곱근까지만 확인하므로 시간 복잡도를 효과적으로 줄일 수 있습니다. 또한, 마지막에 N > 1을 체크하여, 남아 있는 소인수가 있다면 그것을 출력함으로써 최적화된 소인수분해가 완료됩니다.

인프런 커뮤니티 질문&답변

#11653 소인수분해 문제(최적화 관련)