#11653 소인수분해 문제(최적화 관련)
아래와 같이 코드를 작성하였는데 답은 맞췄지만 강의에서 말씀하신 제곱근 아이디어가 반영되어있지 않습니다.
아래 코드를 더 최적화 할 수 있는 아이디어가 있나요?
#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답변 2
1
답변이 늦어서 죄송합니다! ( 요즘 새 회사에 적응하느라 자꾸 놓치게 되네요 ㅠㅠ... 다롱이님 질문 많이 해주셔서 고마워요 )
소인수분해 문제에서 추가로 최적화는 필요 없어 보입니다 🙂
이 다음 문제로 보석 도둑 문제를 풀면서 제곱근 아이디어를 적용해 보시면 좋을 것 같습니다!
0
안녕하세요, 인프런 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을 체크하여, 남아 있는 소인수가 있다면 그것을 출력함으로써 최적화된 소인수분해가 완료됩니다.
dp[x]가 최대값이라고 확신할수 있는 이유
0
45
1
1090번 문제 질문
0
150
1
유니온파인드
0
112
1
투포인터 25:15 질문
1
128
1
#1090번 문제 반례가 궁금합니다.
0
148
1
예제코드 자바입니다
1
186
1
정수론 파트 #2247 문제에 대한 질문입니다!
0
102
0
코드 오류
0
185
1
2강 정수론 문제3 #1407 질문
0
127
0
이차원 배열 (int형)dp로 0 혹은 -1로 체크하는 방법 말고 boolean형 배열로 체크해서 바로 리턴해줄 수 없나요?
0
154
0
1717번 최적화
0
112
0
백준 22988 문제 질문
1
193
2
[Python] 백준 1090번 문제
1
226
3
강의자료에서
1
162
2
2503 문제 제한 조건 질문!
1
249
2
백준 22988 번 문제
1
193
1
추가 강의 순서
1
180
2
(*문제 풀이)1090 테스트케이스 1번 C++
1
221
2
7강 RGB 색칠하기 질문 있습니다.
1
160
2
정수론 약수 빠르게 구하기 질문
1
257
1
1090 문제의 2, 3번째 아이디어는 결국 같은거 아닌가요?
1
373
2
1090 문제 관련하여 맨해튼 거리 최솟값에 대해 질문 있습니다.
1
223
2
누적합 문제 3번 질문
1
216
2
기억 ( 누적합 ) 강의 11660 문제
1
163
2