[백준] 골드바흐의 추측(9020번) - Python

처음 코드 ( 실행시간 1120ms) 

---

import sys

# 소수 리스트 생성 함수
def prime(n):
    sieve = [True] * (n+1)
    for i in range(3,int(n**.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i] = [False]*len(sieve[i*i::2*i])
    return [2]+[i for i in range(3,n+1,2) if sieve[i]]

# 파티션 구하는 함수
def getPartition(prime:list,n:int)->str:
    left, right = 0, len(prime)-1
    partition = ""
    while left <= right:
        if prime[left] + prime[right] > n:
            right -= 1
        elif prime[left] + prime[right] < n:
            left += 1
        else:
            partition = str(prime[left])+" "+str(prime[right])
            left += 1
    return partition

#실행 부분
num = int(sys.stdin.readline().strip())
for _ in range(num):
    number = int(sys.stdin.readline().strip())
    print(getPartition(prime(number),number))

 

 

첫 코드의 알고리즘

1. number를 입력 받는다.
2. number 이하의 소수 리스트를 생성한다. (ex) [2,3,5,7,11,13]
3. 소수리스트의 양끝의 합을 구해가며 left, right의 index가 점점 가운데로 모이다가 left > right가 되는 순간 끝난다

 

 

 

개선된 알고리즘 ( 실행시간 56ms )

---

import sys

#소수 리스트 생성 index가 해당 숫자를 의미한다. index 2 == 숫자 2
sieve = [False,False,True] + [True,False]*4999
for i in range(3,int(10000**.5)+1,2):
    if sieve[i]:
        sieve[i*i::2*i] = [False]*len(sieve[i*i::2*i])
    
num = int(sys.stdin.readline().strip())
for i in range(num):
    number = int(sys.stdin.readline().strip())

#number 가 4일 때 출력이 되지 않기 때문에 오류처리
    if number == 4:
        print("2 2")
        continue
        
#시작 index를 설정해 주는 부분
#양 끝에서 합을 구하며 오는 것이 아니라
#가운데에서 양 끝으로 퍼져나간다
    start = number//2

#소수는 홀수만 따지므로 start가 짝수인 경우 홀수로 만들어 주기
#짝수는 탐색하지 않기 때문에 number 가 4 인 경우에 오류가 발생한다. 그래서 위에서 오류처리
    if start%2 == 0:
        start -= 1

# partition이 여러개 존재하는 경우 index가 가까운 것을 출력하므로
# 가운데에서 바깥쪽으로 탐색
    for j in range(start,0,-2):
# 소수리스트를 만드는게 아니라 seive 자체를 사용하므로 j가 의미하는 것이 숫자임
# 그러므로 합이 number인 수의 index는 j 와 number - j 가 된다.
# 이 때 둘 다 소수인 경우 seive[j] 와 seive[number-j] 는 True 이다.
        if sieve[j] and sieve[number-j]:
            print(j,number-j)
            break

 

 

개선된 알고리즘이 효율적인 이유

1. 첫 코드는 number를 입력 받을 때마다 소수 리스트를 생성하였으나 개선된 코드는 소수 리스트 seive를 만들고 계속 사용한다.
2. 소수 리스트를 생성할 때 소수 리스트를 만드는 과정을 생략하고 seive 리스트 자체를 사용
3. 위의 이유 때문에 합이 number인 수의 seive에서의 index를 j 와 number-j라고 할 수 있음
4. 그러므로 처음 코드에서처럼 불필요하게 number와 두 소수의 합의 크기 비교를 하며 index를 옮길 필요가 없다.
5. 첫 코드는 양 끝에서 가운데로 탐색을 한 반면 개선된 코드는 가운데에서 양끝으로 탐색을 진행한다.

 

위와 같은 이유로 실행시간이 1120ms 에서 56ms로 대폭 감소하였다.