코딩테스트: 소수와 관련된 문제 3가지(04.05)

순서쌍개수,
소수찾기,
소수만들기,

3. 순서쌍 갯수

문제 이해

곱하면 주어진 자연수가 되는 모든 순서쌍의 갯수를 반환 해야한다. 순서가 다르면 다른 것이다.

시도 1. n보다 작은 모든 자연수에 대해 나뉘어 떨어지는지 체크

def solution(n):
    total = 0
    for i in range(1,n+1):
        if n % (i) == 0:
            total += 1
    return total

곱하면 n이 되는 순서쌍을 이루는 두 요소는 모두 자연수이므로, n을 두 요소로 나누면 나뉘어 떨여져 나머지가 0이 되어야한다. 이러한 성질을 이용해 n보다 작은 수 중에서 n을 나머지 없이 나누는 모든 자연수의 갯수를 순서쌍의 갯수와 동치라고 생각할 수 있다.
이 방법은 O(n)의 시간복잡도를 가진다.

해결. 체크 할 숫자 줄이기

시도 1을 살펴보면 우리는 n 보다 작은 수가 아니라 n의 제곱근보다 작거나 같은 수만 따져도 된다는 것을 알 수 있다. 제곱근 보다 작은 약수를 모두 찾았다면 제곱근 보다 큰 약수는 이미 다 찾은것이나 다름없다.

def solution(n):
    total = 0
    for i in range(1,int(1 + n**0.5)): # 제곱근보다 작거나 같은 값 까지만 돌린다
        if n % i == 0:
            print(i)
            total += 1
    if (i)**2 ==n: # 찾은 약수중 제곱근이 있다면 그 약수가 들어간 순서쌍은 오직 한개이므로
        return 2*total -1 # 순서쌍은 홀수개가 된다
    return 2*total # 아님 짝수

range(1,n+1):

range(1,int(1 + n**0.5)):

확실히 빠른 것을 볼 수 있다.

2. 소수 찾기

문제 이해

주어진 숫자보다 작은 모든 소수를 찾고 그 갯수를 반환해야 한다.

시도 1. 이중 반복문으로 소수 찾기

모든 소수는 자신보다 작은 소수와 서로소라는 것을 이용하는 기초적인 방식을 구현했다.

def solution(n):
    prime = [2]
    for i in range(2, n+1):
        is_p = True
        for p in prime:
            if not i % p: # 소수로 나눠진다면 합성수이다
                is_p = False
                break
        if is_p:
            prime.append(i)

    return len(prime)

2보다 크거나 같고 n보다 작거나 같은 모든 수들을 자신보다 작은 소수로 나누어 본다. 그중 하나라도 나뉘어 떨어지면 이는 해당 소수를 인수로 갖는 합성수임을 의미한다. 무사히 통과했다면 소수를 리스트에 저장한다.

이 방식은 for문을 두번 사용하는데, 안쪽 반복문은 소수 갯수만큼만 반복하긴하나 소수의 갯수는 n이 증가하면 같이 증가한다.
그래서 시간초과로 인해 정답이 되지 못한다.

시도 2. 순서쌍 찾기에서 쓴 방법 써보기

어떤 수가 소수인지 아닌지 판별할 때, 자신보다 작은 수중에 1이 아닌 약수가 있는지를 보면된다. 이것은 문제1을 그대로 뒤집은 문제이므로 그때 썼던 방식인 제곱근까지만 확인하기를 써서 연산 횟수를 줄일 수 있을 것이다.

def solution(n):
    prime = [2]
    for i in range(3, n+1): 3 부터 검사 n+1까지 검사
        is_p = True
        for p in prime:
            if p > i**0.5:  # 자신의 제곱근 보다 큰 소수는 굳이 체크하지 않는다
                break
            if not i % p:  # 소수로 나눠진다면 합성수이다
                is_p = False
                break
        if is_p:
            prime.append(i)

    return len(prime)

이렇게 하면 기존 코드에서는 소수의 경우 자신보다 작은 모든 소수들에 대해 체크를 한 것에 비해 자신의 제곱근 보다 작은 소수만 체크하면 되므로 연산횟수가 줄어든다. 모든 테스트케이스를 시간내에 통과해 정답 코드로 인정받았다.

하지만 여전히 굉장히 많은 시간이 들어감을 알 수 있다.

해결. 에라스토테네스의 체

에라스토테네스의 체는 주어진 수 보다 작은 소스들을 찾아내기 위한 알고리즘이다.

1. 1부터 주어진 수 까지의 목록을 만들고 1은 소수가 될 수 없으니 뺀다.
2. 1 다음엔 2이다. 2는 소수다. 2를 제외한 2의 배수는 합성수이므로 2를 제외한 2의 배수를 목록에서 제거한다.
3. 2 다음에 오는 숫자는 소수인 3이다. 마찬가지로 3을 제외한 3의 배수를 목록에서 제거한다.
4. 3 다음은 5 이다. 마찬가지...
   위의 과정을 반복하다가
   x를 제외한 x의 배수를 지워야 할때의 x가 n의 제곱근 보다 커지면 정지한다.
   문제 1에서 본 합성수의 약수의 특성과 소수의 특성을 이용해 아주 빠르게(O(n) 혹은 O(nloglogn)([참고])) 주어진 수 보다 작은 소스들을 찾아낸다.

   def solution(num):
    primeset = set(range(2, num+1)) # 2~n까지의 목록
    i = 0
    primes=[]
    prime=2
    while prime<=num**0.5:  # n의 제곱근 까지만 본다
        prime = min(primeset)  # 목록중 가장 작은수==가장작은 소수를 빼서
        primes.append(prime)  # n의 제곱근 보다 작은 소수 목록에 저장
        primeset = primeset - set(range(prime, num+1, prime))  # prime을 포함한 prime의 배수 싹다 제거
    primes=primes+list(primeset)  # 다 돌았으면 n의 제곱근보다 큰 곳도 소수만 남았으므로 합친다
    return len(primes) # 갯수 출력

   

   
   훨씬 빠른 것을 볼 수 있다.

   3. 소수 만들기

   

문제 이해

n개중 3개를 순서상관없이 뽑는(조합) 모든 경우의 수 중에서 조합의 총합이 소수가 되는 경우의 갯수를 세야한다.
조합을 뽑는 것은 이미 해봤으므로 그냥 for문 3개 돌리기로 하고, 중요한 것은 소수인지 아닌지 판별하는 것이다.

시도 1. 문제 2와 유사하게 에라스토테네스의 체 이용하기

이론상 가능한 최댓값보다 작은 소수들을 모두 구해놓고, 그 소수에 조합의 합의 포함되는지 체크해보자.

def solution(nums):
    nums.sort(reverse=True)
    ideal_max = sum(nums[:3])  # 조합의 합의 최댓값
    primeset = set(range(2, ideal_max+1))  # 목록 생성
    primes=[]
    prime=2
    while prime<=ideal_max**0.5: # 최댓값의 제곱근 보다 작거나 같은 값만
        prime = min(primeset)  # 목록중 가장 작은수==가장작은 소수를 빼서 
        primes.append(prime)  # n의 제곱근 보다 작은 소수 목록에 저장
        primeset = primeset - set(range(prime, ideal_max+1, prime))  # prime을 포함한 prime의 배수 싹다 제거
    primes=primes+list(primeset)  # 다 돌았으면 n의 제곱근보다 큰 곳도 소수만 남았으므로 합친다

    count = 0

    # 조합
    for i, x in enumerate(nums[:-2]):
        for j, y in enumerate(nums[i+1:-1], i+1):
            for k, z in enumerate(nums[j+1:], j+1):
                sum_=x+y+z
                if sum_ in primes: # 이론적 최댓값보다 작은 소수목록에 있는지 확인
                    count +=1

    return count

기존목록과 다른 새로운 목록을 추가하고 그곳에 제곱근보다 작은 소수를 저장해두고 제곱근보다 큰 소수만 남은 원래 목록을 합치는 이유는 set이 인덱스로 접근할 수 없어서 i 번째 소수=2 -> 3 ... 이런식으로 할수가 없고,
또한 반복문 안에서 인덱스에 변화를 주는 행위를 해야하기 때문에 리스트로 바꿔 인덱스로 접근하는 행위 또한 지양해야하므로 최솟값을 뽑아내 따로 저장해 두는 방식으로 구현했다.

시도 2. 문제 1과 유사하게 각 조합을 판별하기

각 조합의 합 마다 소수인지 판별해보자.

def solution(nums):
    count = 0
    for i, x in enumerate(nums[:-2]):
        for j, y in enumerate(nums[i+1:-1], i+1):
            for k, z in enumerate(nums[j+1:], j+1):
                sum_=x+y+z
                for i in range(2,int(sum_**0.5 + 1)): # 문제 1과 유사한 방법으로 접근해 소수 판별
                    if not sum_%i:
                        count -=1
                        break
                count+=1
                if sum_ in primes:
                    count +=1
    return count

해결. 둘 중 어느 것이 빠른가?

 

위가 에라토스테네스의 체를 이용한 것이고, 아래가 그냥 각 조합의 합마다 소수인지 판별한 것이다.
속도는 전체적으로 아래가 더 빨랐다. 이는 문제를 풀기위해 설정한 '이론적인 최댓값'이 실제 소수인 조합들의 합 보다 매우 크기 때문에 그런 것으로 보인다.

배운점

1. 새로운 알고리즘 에라토스테네스의 체에 대해서 알게 되었다.
2. 반복문 내에서 변화하는 객체에 대해 인덱스로 접근할 생각은 안하는 것이 좋다

레퍼런스

[Wikipedia-Sieve of Eratosthenes]