꾸준히 개발하기

소수판별 알고리즘과 시간초과의 늪의 반복이었던 문제... 계속 풀었던 골드바흐 파티션 문제 중 아마 시간이 제일 짧게 주어졌던 문제였던 듯 하다. 물론 그거 고려 안하고 무작정 들박했다가 처참한 시간 초과의 늪에 빠졌다.

처음에는 최대 MAX 값만큼 안 돌리고 테스트케이스 내에서 max값까지만 에라토스테네스의 체를 이용하는 것도 고려해봤는데 여전히 시간초과가 나더라. 생각해보면 max값까지 돌리나 백만까지 돌리나 시간은 크게 차이가 없었다. 그러면 이제 따져볼건 골드바흐 파티션을 구하는 과정에서 불필요한 for문이 있다는 거였다. 아무리 생각해도 for문을 2개를 돌려야될 것 같다고 생각하면서 break문 열심히 넣어줘도 계속 시간초과가 났다.

for문을 1개로 줄여야 통과될 것 같은데, 하면서 보다가 답을 찾아냈다.

-> 굳이 for문을 2개 돌릴 필요 없이, 앞에서부터 보는거 + 뒤에서부터 보는거 는 for문 1개로 충분했다!

흐뭇하게 .. 시간초과의 늪에서 벗어났다. 코드는 다음과 같다.

def getPrimes(MAXCASE):
    erato = [True] * (MAXCASE + 1)
    erato[0], erato[1] = False, False

    for i in range(2, int(MAXCASE ** 0.5) + 1):
        if erato[i] == True:
            for j in range(i + i, MAXCASE + 1, i):
                erato[j] = False
    return erato


erato = getPrimes(1000001)
t = int(input())

for _ in range(t):
    num = int(input())
    cnt = 0
    for i in range(2, num // 2 + 1):
        if erato[i] and erato[num - i]:
            cnt += 1
    print(cnt)

굳이 에라토스테네스의 체를 함수로 선언해준 이유는... 입력받은 숫자 중 max값까지만 소수판별을 하려고 했었다 원래는 ^.T 중첩 for문을 줄여야 시간복잡도를 확 줄일 수 있다고 또다시 몸으로 깨달은 문제였다. 

소수 판별 알고리즘 중 에라토스테네스의 체 방식을 알고 있어야 시간 초과가 안 나는 문제다. 물론 나는 에라토스테네스의 체 방식을 매번 입력받을 때마다 하고 반복문도 많이 써서 시간초과만 우다다 받았다 ^^ 

시간초과를 막는 중요한 포인트가 2개였다...

1. 에라토스테네스의 체를 범위 내의 모든 숫자에 한해서 1번만 돌리기
2. 최대한 반복문 줄이기

최대 입력 가능한 숫자 범위가 1000000이니까 그 안을 일단 다 소수를 판별해버린다! 가능한 소수를 미리 다 계산한 뒤 또 범위 내에서 새로운 리스트를 만들지 말고, 반복문 안에서 True, False값을 체크해서 보기만 해야 시간 초과가 안 난다.

시간초과가 이렇게 머리를 아프게 하는지 간만에 느껴본 문제...^^ 같은 골드바흐 문제는 꽤 금방 시간초과를 잡아서 기가 살아있었는데 1시간 내내 계속 시간 줄이다 보니까 기가 쪼그라들었다... 그래도 풀긴 푼거니까... 어디서 시간초과가 나는지 잘 살펴보는 능력도 정말 중요하구나, 또 느낀다.

파이썬 코드는 다음과 같다.

erato = [True] * 1000001
erato[0], erato[1] = False, False
for i in range(2, 1001):
    if erato[i]:
        for j in range(i + i, 1000001, i):
            erato[j] = False

while True:
    n = int(input())
    wrongFlag = True
    if n == 0:
        break

    for i in range(3, n):
        if erato[i] == True:
            if erato[n - i] == True:
                wrongFlag = False
                print(n, "=", i, "+", n - i)
                break
    if wrongFlag:
        print("Goldbach's conjecture is wrong.")

눈물의 코드... (쓸 필요도 없었고 시간초과만 유발했던 녀석들이다)

# n 미만의 수 중 홀수인 소수 리스트 리턴
def getPrimeNums(n):
    return [i for i in range(n) if erato[i] == True and i % 2 != 0]


def getGoldB(target, nums):
    middleIdx = -1
    for i in range(len(nums)):
        if nums[i] > int(target / 2):
            break
        middleIdx = i

    for i in range(middleIdx + 1):
        for j in range(len(nums) - 1, middleIdx, -1):
            if nums[i] + nums[j] < target:
                break
            if nums[i] + nums[j] == target:
                return [nums[i], nums[j]]
    return False

나름 시간 좀 줄여보겠다고 다른 골드바흐 문제에서 시간초과 잡아줬던, 중간값 구해서 어찌저찌 해봤는데 역시나 시간초과였다. 그냥 T/F 값 판단해서 바로바로 계산하는게 제일 빠르구만

https://school.programmers.co.kr/learn/courses/30/lessons/42839

풀이

모든 경우의 수를 permutations를 사용하여 순열로 뽑아내었다. list로 나온 요소를 모두 join 메서드를 사용하여 이어붙인 뒤 숫자로 변환하였다. 문제에서 011과 11은 같은 숫자라고 명시했기 때문에 중복을 제거한 뒤 모든 경우를 소수 판별했다. 0과 1은 소수가 아니므로 예외처리를 해주고 그 외의 경우에는 1, 자기자신을 제외한 수로 모두 나눠보며 체크했다.

프로그래머스 내에서는 통과되었는데 분명 시간초과가 날 여지가 있다고 생각하여 소수판별 알고리즘을 한번 더 정리해보려 한다. 블로그에 이미 올려둔 내용이긴 하지만... 또 까먹었기 때문에 한번 더 정리

# 2022-07-22
# 프로그래머스 Lv2 - 소수 찾기
# https://school.programmers.co.kr/learn/courses/30/lessons/42839
# 소요시간 : 15:10 ~ 15:25 (15m)

from itertools import permutations

# 소수판별 알고리즘
def checkPrimeNum(num):
    if num == 0 or num == 1:
        return False

    for i in range(2, num):
        if num % i == 0:
            return False
    return True


def solution(numbers):
    answer = 0
    num_arr = []
    for num in numbers:
        num_arr.append(num)

    every_case = []
    for i in range(1, len(num_arr) + 1):
        case = list(permutations(num_arr, i))
        for arr in case:
            every_case.append(int("".join(arr)))

    every_case = list(set(every_case))

    for case in every_case:
        if checkPrimeNum(case):
            answer += 1

    return answer

소수 판별 알고리즘

단일 숫자 판별 시

약수의 성질을 살펴보면 모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다. 

16의 약수는 1, 2, 4, 8, 16 인데 2x8 = 16, 8x2=16이다.

따라서 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인해주면 된다. 

# 소수 판별 (개선된 알고리즘)
import math

def isPrimeNumber(num):
    # 2부터 num의 제곱근까지의 모든 수를 확인하기
    # 제곱근을 구하는 방법은 math.sqrt() 사용. 반환형은 float
    # 음수의 제곱근을 구하게 되면 error 발생하니 유의
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

대량의 숫자 판별 시 (에라토스테네스의 체)

이 문제에서는 각각의 경우가 소수인지 판단해야 되서 아니지만, 만약 특정 범위까지의 자연수 중 소수가 몇개인지처럼 대량의 소수를 한꺼번에 판별하고자 할 때 사용하면 좋은 방법을 추가로 정리한다.

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당, 그 인덱스에 해당하는 값을 넣어준다. 2부터 시작하여 특정 숫자의 배수에 해당하는 숫자를 모두 지운다. (자기 자신은 지우지 않음) 

n = int(input())

eratos = [True] * (n+1)
m = int(n**0.5) // math.sqrt 사용해도 ok

for i in range(2, m+1):
	if eratos[i] == True:
    	for j in range(i+i, n+1, i): #i의 배수를 모두 삭제, 본인은 제외
        	eratos[j] = False
            
print([i for i in range(2, n+1) if a[i] == True])