글 읽기 - 두 코드 사이의 차이를 잘 모르겠어서 질문드립니다.(파이썬)

alpha_coder 1년 전 0

아래의 두 코드 모두 에라토스체 알고리즘을 통해 소수를 구하였는데, 하나는 시간초과가 나고 다른 하나는 시간초과가 나지 않는 이유를 잘 모르겠습니다. 제가 생각할 때, 시간초과가 나는 코드는 추가로 소수를 저장하기 위한 리스트를 생성했는데, 이 부분이 문제일까요? (소스코드 17번째 줄과 37번째 줄을 비교하면 소수만 확인하기 때문에 오히려 시간이 줄어들 줄 알았는데, 오히려 시간초과가 나서 당황스럽습니다. 조언 부탁드립니다.)

# 시간초과가 나는 파이썬 코드
MAX = 1000000
prime_arr = []
is_prime_arr = [True]*(MAX+1)
is_prime_arr[0], is_prime_arr[1] = False, False
for i in range(2, MAX+1):
    if is_prime_arr[i]:
        prime_arr.append(i)
        j = i*i
        while j <= MAX:
            is_prime_arr[j] = False
            j += i
while True:
    n = int(input())
    if not n:
        break
    for i in prime_arr[1:]:
        if is_prime_arr[n-i]:
            print(f'{n} = {i} + {n-i}')
            break

# 시간초과가 나지 않는 파이썬 코드
MAX = 1000000
prime_arr = [True]*(MAX+1)
prime_arr[0], prime_arr[1] = False, False
for i in range(2, MAX+1):
    if prime_arr[i]:
        j = i*i
        while j <= MAX:
            prime_arr[j] = False
            j += i
while True:
    n = int(input())
    if not n:
        break
    result = None
    for i in range(3, int(n/2)+1):
        if prime_arr[i] and prime_arr[n-i]:
            result = f'{n} = {i} + {n-i}'
            break
    if result:
        print(result)
    else:
        print("Goldbach's conjecture is wrong.")

myyh1234 1년 전 0

prime_arr[1:]에서 배열을 복사하는 시간복잡도는 O(N)입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두 코드 사이의 차이를 잘 모르겠어서 질문드립니다.(파이썬)

alpha_coder 1년 전 0

myyh1234 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말