글 읽기 - (파이썬) 소수구하기 - 시간초과 해결방법이 있을까요??

osh1795 2년 전 0

며칠전에 질문했었는데 아직 해결이 안되서 다시 올립니다....

문제에서 얘기한데로 에라토스테네스의 체로 한번 코드를 작성해봤습니다. 제가 #1, #2모두 출력해봤는데 답은 맞았습니다. 근데 여기서 제출을 해보니 시간초과가 뜹니다.

#1은 2부터 주어진 범위까지 모두 case 리스트에 넣고 소수를 모두 구한 다음 범위 밖의 수를 제거해서 case안에 해당하는 소수들만 남기고 for문을 이용해서 출력했습니다.

#2는 똑같이하는 대신 소수임이 확정되면 주어진 범위에 들어가나 확인하고 들어가면 즉석에서 출력하는 형식으로 작성했습니다.(이 경우 case에 범위 밖의 소스들도 포함되어 있습니다.)

질문1. #1과 #2 모두 시간초과가 뜨는데 혹시 어디가 문제인지 알 수 있을까요?? 해결방법도 알려주세요...

질문2. #1과 #2의 계산량(?)이 차이가 많이 나나요? 차이가 많이 난다면 그 이유도 알려주실수 있나요???

감사합니다!

#공통부분
a,b=map(int,input().split())

#1
#   2부터 주어진 범위까지 소수 리스트를 구하고 a 아래의 숫자를 제거해서 case에 범위내의 소수만 남기고 출력

cnt=0 #소수의 갯수-1
case=[i for i in range(2,b+1)] #2부터 b까지의 모든 자연수
while cnt!=len(case):
    for i in case[cnt+1:]: #cnt부터 넣으면 본인도 사라짐
        if i%case[cnt]==0:
            case.remove(i)
    cnt+=1
while case[0]<a:
    case.remove(case[0])
for i in case:
    print(i)
    
print('--------------------------------------------------------------------------------')

#2
#   2부터 주어진 범위까지 소수 리스트를 구하고 소수가 결정이 되면 주어진 범위에 들어가는지 확인하고 맞으면 바로 출력
cnt=0 #소수의 갯수-1
case=[i for i in range(2,b+1)] #2부터 b까지의 모든 자연수
while cnt!=len(case):
    for i in case[cnt+1:]: #cnt부터 넣으면 본인도 사라짐
        if i%case[cnt]==0:
            case.remove(i)
    if case[cnt]>=a:
        print(case[cnt])
    cnt+=1

sweetlulu486 2년 전 1

remove의 연산량이 큽니다

osh1795 2년 전 0

그럼 remove를 대신할만한게 있나요???

sweetlulu486 2년 전 0

python은 list를 배열리스트(arraylist) 방식으로 구현하고 있으며 단점이 삭제가 O(N)이나 걸리는 자료구조입니다.

장점으로는 접근해야할 인덱스를 정확히 알고 있으면 O(1) 시간 만에 값을 찾을 수 있습니다.

이러한 특징을 이용해 에라토스테네스의 체는 0부터 N포함까지의 수를 포함할 수 있는 배열리스트(또는 배열)를 선언해서, 소수인 수는 소수임을 표시, 그게 아닌 경우 소수 아님을 표시를 해서 원하는 수를 체킹합니다.

remove를 할경우 시간 복잡도는 O(N^2)이 되며,

에라토스테네스의 체 시간복잡도는 대략 O(NloglogN) 이 되고 시간 복잡도에서 많은 개선을 할 수 있습니다.

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

문제

문제

출처

ICPC

(파이썬) 소수구하기 - 시간초과 해결방법이 있을까요??

osh1795 2년 전 0

sweetlulu486 2년 전 1

osh1795 2년 전 0

sweetlulu486 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말