이번에도 시간 차이를 보고 싶어 2가지 방법으로 풀어보았다.
처음에는 N보다 작은 소수를 리스트에 집어넣고 소수 안에서 계속 나누면 된다고 생각했는데 시간 초과가 떴다.. 오히려 소수들로만 나누기 때문에 시간 초과를 막을 거라고 생각했는데..
1. 시간 초과
N = int(input())
lst = []
if N != 1:
for n in range(2, N+1):
is_prime = True
for i in range(2, n//2 + 1):
if n % i == 0:
is_prime = False
break
if is_prime:
lst.append(n)
while N != 1:
for i in lst:
while N % i == 0:
print(i)
N //= i- 굳이 소수로 안 나눠도 되는 이유는, 어차피 2부터 돌기 때문에 합성수는 앞에서 이미 다 나누어준다.
예를 들어 for문을 돌면서 4를 만나더라도 이미 앞에서 2로 다 나누어놨기 때문에 4로 나누어질 일은 없다.
그렇다면 왜 시간초과가 떴을까?
역시나 소수의 리스트를 만드는 데 시간이 오래 걸리기 때문이다.
1. 2 ~ N까지 모든 수를 돌면서 소수 판별 → 소수만 리스트에 저장
2. 소수 판별은 n//2까지 나눠봄 → 최악의 경우 O(N²)에 가까운 연산
3. 그 다음에 소인수분해 시작 → 소수 리스트 길이가 커서 루프도 많이 돔
최악의 경우 O(N²)의 시간 복잡도가 발생한다.
- 바깥쪽 for문(for n in range(2, N+1))에서 약 N번 발생
- 안쪽 for문(for i in range(2, n//2+1))최악의 경우 n/2번까지 검사
하기 때문이다.
그래서 사실 n//2까지가 아니라 √N까지만 도는 게 더 최적화된 방식이다.
2. for문 & while문
N = int(input())
if N != 1:
for i in range(2, N+1):
while N % i == 0:
print(i)
N /= i
if N == 1:
break- 합성수로 매번 나누어 주는 게 시간 초과를 유발할 거라 생각했지만, 사실은 합성수로 나눌 때는 거의 바로 N % i != 0이라서 곱셈/나눗셈 한 번 하고 넘어가기 때문에 시간이 그렇게 오래 걸리는 것이 아니다.
- 그리고 range(2, N+1)까지 해서 오래 걸린다고 생각한 건데.. 1번째 코드는 이 안에서 for 루프까지 또 돈다. 그리고 나와서 while 루프를 또 돈다! 최적화는 정말 중요하다는 것을 다시 한번 깨닫는 문제였다. 우습게 보지 말고 깊게 생각하자.
3. while문 한 번만
N = int(input())
i = 2
while N != 1:
if N % i == 0:
print(i)
N /= i
else:
i += 1결과
나는 1번 방법이 for문을 한 번 더 쓰기 때문에 시간이 더 오래 걸릴 거라고 생각했는데 웬걸.. 2가 훨씬 오래 걸렸다.
아무리 봐도 똑같은 횟수만큼 루프를 도는 것처럼 보였는데.. gpt를 계속 괴롭힌 결과.. 횟수에서의 차이점이 아니라 for과 while에서의 i+=1 계산의 차이점이라고 한다. i+=1이라는 연산을 위해 새 객체를 생성하고 바인딩함으로써 루프 오버헤드가 커진다고 한다.
제곱근 사용
gpt가 알려준 대로 제곱근을 사용해 봤는데.. 엥? 완전오나전 시간이 단축되었다. 기억하자 소수는 제곱근..
import math
N = int(input())
if N != 1:
i = 2
while i <= math.isqrt(N):
while N % i == 0:
print(i)
N //= i
i += 1
if N > 1:
print(N)