230125 에라스토테네스의 체, and와 Short Circuit Evaluation

백준의 기초알고리즘 수학1 강의를 들었다.

아무래도 계절학기로 이산수학을 들었기 때문에, 개념자체는 어려울 게 없었다.

 

유클리드 호제법을 통한 최대공약수, 최소공배수 구하는 알고리즘 (시간복잡도 O(logn) )

소수판별 알고리즘(시간복잡도 O(sqrt(n))이지만, sqrt(n)할바에 n/2 )

범위가 제한된 환경에서 사용하는 에라스토테네스의 체 ( 시간복잡도 O( log(log(n)) )

 

이렇게 세가지를 배워보았다.

 

뭐 유클리드 호제법이랑, 소수판별 알고리즘은 프로그래머스 기초100제에서도 이미 풀어봤고

그리 복잡할게 없었으나

 

에라스토테네스의 체는 개념으로는 이해가 가면서도

실제로 구현을 위해서는 코드의 구성이 O(n^2)이 안되도록 설계해야 하는데,

상당히 당황스러울 수 밖에 없다.

 

에라스토테네스의 체를 사용해야 하는 

백준 1929번, 소수 구하기 문제이다.

 

# 1929 

from sys import stdin

m,n = map(int, stdin.readline().rstrip().split(' '))
	
prime_list = [True]*(n+1)

maxroot = int(n**0.5)

for i in range(2,maxroot+1):
	for j in range(m,n+1):
		if prime_list[j] == True and j!=i
			prime_list[j] = False

for i in range(m,n+1):
		if prime_list[i] == True:
			print(i)

 

처음에는 위와 같이 작성하였다.

자세히보면, 결국 이중 for문을 사용하여 최악의 경우 O(n^2)이 되어버리는 것을 알 수 있다.

 

모든 2부터 maxfoot 사이의 i에 대해서 m와 n범위에 있는 배수들을 다 지우는 건데,

결국 m=1이라고 생각할 때 최악의 경우 소수판별기랑 다른게 없다.

m과 n사이의 수들을 다 체크해야 한다.

 

위와 와 같이, 소수들의 리스트에서 하나가 True라서 소수로 판별나면,

n미만의 범위에서 그 소수의 배수들만 싸그리 False로 꺼버리는 작업이 필요하다.

그게 아니라서 시간초과났다.

 

# 1929 

from sys import stdin

m,n = map(int, stdin.readline().rstrip().split(' '))
	
prime_list = [True]*(n+1)

maxroot = int(n**0.5)

for i in range(2,maxroot+1): # divider
	if prime_list[i]==True: #i가 소수라면,
		for j in range( 2*i, n+1, i):
			prime_list[j] = False # 2i부터 m까지 i의 배수는 다 소수아님.
			
prime_list[1] = False

for i in range(m,n+1):
		if prime_list[i]:
			print(i)

 

위와 같이 2*i부터 n이하의 수까지, i의 배수들을 다 지우는 과정을 거친 뒤,

1은 원래 소수가 아니므로 False해버린다.

이중 for문에서, m부터 n까지 다 훑는게 아니라, i의 배수만 훑게 된다.

 

하여튼, 골드바흐문제는 

https://fashionking.tistory.com/241

여기까지 이어진다.

################################

 

파이썬은 참 시간이 부족한 언어이다.

C로 기초적인 프로그래밍을 할 때에도, 컴파일 에러가 뜨지 시간부족이 뜰일은 많이 없었으나..

얘는 뭐만하면 시간이 부족한거 같다. 내 코드가 스파게티라서 그런것도 있겠지만..

 

아래의 글은 6588번 골드바흐의 추측 문제에 대하여 질문게시판에 올라온 질문이다.

파이썬의 시간부족을 타파하기 좋은 황금같은 답변이 있어 기록해놓는다.

--

 

ehdguscjs1   1달 전

에라토스테네스 체를 통해 코드를 작성하였는데 어느 부분에서 시간초과가 나오는지 모르겠습니다....

tot=[True]*1000001
for i in range(2,1001):
    if tot[i]:
        j=i
        while i*j<=1000000:
            tot[i*j]=False
            j+=1
t=0
while True:
    num=int(input())
    if num==0: break
    for i in range(2,num//2+1):
        if tot[i] and tot[num-i]: 
            print('%d = %d + %d' % (num,i,num-i))
            t=1
            break
    if t==0: print('Goldbach\'s conjecture is wrong')

---

 

dongwanpianist  

 

일단 표면적으로 볼 때는

첫 반복문에서 소수를 구할 때 2의 배수를 입력할 필요가 없는데
꼬박꼬박 False를 입력하셨습니다.
3,5,7,9이렇게 홀수인 i만 연산하게끔 i+=2로 증가하도록 반복문을 바꾸면
입력시간이 절반정도 줄어듭니다.
짝수중에는 딱 2라는 수 하나만 소수(true)인데, 홀수소수의 합만 구하는 문제라서 여기선 2도 쓰이지 않습니다.

다음 반복문에서 덧셈이 되는 i을 찾을때도
2의 배수 false가 당연한데 꼬박꼬박 탐색을 하고 있습니다.
비록 부울값 하나를 액세스하는 짧은 작업이지만요.
이 반복문 역시 홀수만 +=2씩 탐색하도록 바꾸시면
시간이 약간 줄어들 수 있습니다.

 

다음으로 반복문(for/while)속의 연산작업을 더욱 줄이는 차원에서

and로 엮어진 if조건문은
오히려 이중if로 분리하면 연산속도가 감소합니다.

예를 들어 if tot[i] and tot[num-i]라고 한줄로 쓰면
1. tot[i]가 true인지 검사하고
2. num-i를 연산하고
3. tot[(2.의값)]가 true인지 검사하고
4. (1.의값)과 (3.의값)이 둘다 true인지 검사하고
5. (4.의값)이 true일때만 if속으로 들어가고, 아니면 점프

이랬던 것을
if tot[i]:
그 안에 if tot[num-i]:
이렇게 분리하여 쓰면
1. tot[i]가 true인지 검사하고
2. (1.의값)이 true일때만 if속으로 들어가고, 아니면 점프
1-1. num-i를 연산하고
1-2. tot[(1-1.의값)]가 true인지 검사하고
1-3. (1-2.의값)이 true일때만 if속으로 들어가고, 아니면 점프

이렇게 바꿀 수 있습니다. and연산 자체가 하나 없어지고, tot[i]가 false면 뒷 검사 자체를 안 해도 되는 거죠.

이런 작업으로 정답시간 안에 들어올 지는 모르겠으나, 우선적으로 작업해야 하는 내용들입니다. 열심히 작성했으니 도움이 되었다면 꼭 답을 달아주세요 :)

 

그리고, 알고리즘 외적인 요인으로는 파이썬에서 대량의 입출력이 동시에 이루어질 때 입출력 속도를 개선하는 방법을 검색해보시기 바랍니다.
int(input()) 그리고 print(...)를 수시로 파박파파팍 번갈아 할 때마다 입출력 담당 os차원에서 약간의 시간이 소요됩니다.
한두번 입출력은 찰나의 시간이라 문제가 없지만, 입출력 횟수가 매우 커지면 시간차이를 측정 가능할 수 있을 정도로 벌어집니다.
스트링 버퍼를 마련해서, 줄바꿈을 포함해서 모든 결과를 차곡차곡 쌓아뒀다가 나중에 한방에 내보내는 방법이 있습니다.

시간초과 건에 대해서는 숫자가 커서 그런 것 보다는
0이 나올 때까지 입력하는 케이스가 많은 경우 그걸 하나하나 입출력하느라 시간이 지체되어 그렇습니다.

 

---

 

if문을 이중으로 쓰는게 시간이 단축된다고?

시스템프로그래밍 과목에서 배운 내용으로는

C언어에서는 a&&b에서 a가 false면 b는 체크하지 않고 바로 a&&b를 false로 취급한다고 하였다.

 

그런데, 잘 찾아보니

이러한 특성을 Short Circuit Evaluation이라고 하며

단순히 C언어가 효율적이네 하고 끝날 문제가 아니라는 것을 알았다.

 

(https://velog.io/@devmin/%EB%8B%A8%EB%9D%BD-%ED%8F%89%EA%B0%80short-circuit-evaluation%EC%97%90-%EB%8C%80%ED%95%9C-%EA%B9%A8%EB%8B%AC%EC%9D%8C-hyk4mrtxtl)

 

(https://code-lab1.tistory.com/68)

 

챗gpt선생님 질문)

Q) and가 아니라 &연산자도 short-circuit evaluation이 되나요? 파이썬에서 Short Circuit Evaluation 을 사용할 수 있는 방법은 없나요? 

(짤린 앞부분에 and랑 &는 논리연산자냐 비트연산자냐의 차이여. 파이썬은 그런기능없음 뭐라뭐라 함)
However, you can achieve short-circuit evaluation in Python by using the or operator along with the if-else statement. For example:
반면에, 당신은 파이썬에서 short-circuit evaluation을 if-else문을 사용하는 방식으로 구현할 수 있습니다.
예를 들자면, ( if a and b : c=True의 파이썬 코드를 SCE로 구현하고 싶다면)

if a:
    c = True
else:
    if b:
        c = True
    else:
        c = False​

Here, if the value of a is True, the interpreter will not bother to check the value of b, and the code block following the first if statement will be executed.
보이는 것과 같이, 위에서 a의 값이 True라면, 인터프리터는 b를 체크하지도 않을 것입니다. 그리고 첫 명령문만 수행될 것입니다.

Additionally, you can use the ternary operator to achieve short-circuit evaluation
그 이외에도, 당신은 삼항연산자를 이용해 SCE를 구현할 수 있습니다.

c = True if a else (True if b else False)​

Here, if the value of a is True, the interpreter will not bother to check the value of b, and the c variable will be set to True.
보이는 것과 같이, 만약 a가 True라면, 인터프리터는 b를 체크하지 않고도 c를 True로 만들어 버릴 것입니다.

It's worth noting that in most cases the performance difference between using the bitwise operator & and using if-else statements or ternary operator will be negligible, so you should choose the one that makes your code more readable and easier to understand.
솔직히 까놓고 말해서 비트연산자나 if-else문 혹은 삼항연산자로 바꾼다고해서 퍼포먼스에 차이가 생기지 않습니다. 그러니 당신은 코드를 더 가독성이 높고 이해하기 쉽게 짜는 방향을 선택하십시오.