규도자 블로그

파이썬(Python) 내장함수의 시간복잡도 나는 내장함수는 뭔가 당연히 최적화돼있겠거니 하고 생각없이 쓰곤 한다. 하지만 그런 자세가 프로그램의 효율에 커다란 영향을 끼치지 않나 싶다. 특히 이번에 에라토스테네스의 체를 응용한 문제를 풀고 있는데 정확한 개념을 알기 위해 위키에 쳐보니 다음과 같은 함수가 나왔다. def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사 m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: # i가 소수인 경우 for j in range(i+i, n, i)..