[ 이것이 코딩테스트다 ] 5일차

안영우·2020년 12월 29일

동빈나 코딩테스트

[ 이것이 취업을 위한 코딩 테스트다. with 파이썬 ]

목록 보기

5/39

[ 이 시리즈에서 작성하는 내용은 이것이 코딩 테스트다 - 나동빈 에서 발췌한 내용을 인용했습니다. ]

✏️ 서론

어제는 코딩테스트에서 주로 사용하는 6가지 라이브러리를 배웠다.
내장함수, itertools, heapq, bisect, collection, math인데

오늘은 math 라이브러리를 사용해서 소수판별 알고리즘을 공부하고자 한다.

✏️ 본론

소수(Prime Number)란 2보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수를 말한다.

간혹 코딩테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야하는 경우가 생긴다. 혹은 1부터 N까지의 모든 소수를 출력해야 하는 문제 등이 출시될 수 있다. 그렇다면 가장 먼저 어떠한 수 X가 주어졌을 때, 해당 수가 소수인지 아닌지 판별하는 방법을 알아보자.

📍 기본 함수

소수를 계산할때 가장 간단한 방법은 X를 2부터 X - 1 까지의 모든 수로 나누어 보는것이다.

import math

def is_prime_number(x):
    for i in range(2, x):
        if x % i == 0:
            return 'not prime'
        else
            return 'prime'

print(is_prime_number(4))
👉🏽 not prime

print(is_prime_number(7))
👉🏽 prime

결론적으로 이 알고리즘의 시간복잡도는 O(X)이고 비효율적이다.
예를들어, input()값이 10,000,000이라고 가정하자.
계산 할 때는 2부터 9,999,999까지의 모든 수에 대해 하나씩 나누어야 한다.

우리는 이러한 비효율적인 알고리즘을 개선해서 시간복잡도를 최대로 줄여 효율적인 알고리즘으로 만들어보자.
자연수가 가지는 특징을 파악하고 있다면 그 원리를 쉽게 이해 할 수있다.

결론적으로 제곱근까지만(가운데 약수까지만) 확인하면 된다.
(나도 처음에 무슨 말인지 몰랐다. 일단 따라해보자)

16이라는 수의 약수(Divisor)는 다음과 같다.

1 2 4 8 16

이때 모든 약수에 대해, 가운데 약수를 기준으로 대칭적으로 2개씩 앞뒤로 묶어서 곱하면 16을 만들 수 있다.

1x16, 2x8, 4x4, 8x2, 16x1

분명한 점은 가운데 약수(4)를 기준으로 각 등식이 대칭적인 형태를 보인다는 것이다.

다른 숫자 8을 예로 들자

1 2 4 8

8의 제곱근(2.8...)을 기준으로 나누면 2까지만 확인하면 된다.
3부터는 확인할 필요가 없다.

1x8 2x4 4x2 8x1

📍 math.sqrt 함수

따라서, 다음과 같이 코드를 작성하면 시간복잡도가 O(X^1/2)인 절반(Half)에 가까운 시간을 줄일 수 있다.

import math

def is_prime_sqrt(x)
    for i in range(2, int(math.sqrt(x))):
        if x % i == 0:
            return 'not prime'
        else
            return 'prime'
print(is_prime_number(4))
👉🏽 not prime

print(is_prime_number(7))
👉🏽 prime

제곱근까지만 확인해도 된다는 점에서 시간 복잡도를 매우 많이 개선할 수 있다.
만약 input()값이 1,000,000일때는 반복문상에서 2 ~ 1,000까지만 확인하면된다.

하지만, 하나의 수가 아닌 수의 범위가 주어졌을때, 전체 수의 범위 안에서 존재하는 모든 소수를 찾아야하는 경우에는 어떻게 할까?

📍 에라토스테네스의 체(Eratosthenes Sieve)

에라토스테네의 체 알고리즘은 여러개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다.

동작원리는 다음과 같다.

2부터 N까지의 모든 자연수를 나열한다.

남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)

더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

코드 이해가 잘 안되면 다음 강의를 보자.
(알고리즘 실력이 많이 부족한 나에게 두번째 강의가 조금 더 도움됐다.)

나동빈, 실전알고리즘

코린아, 코딩하자

에라토스테네스의 체 알고리즘을 1부터 N까지의 모든 소수를 출력하는 프로그램을 작성하면 다음과 같다.
예제에서는 N = 1,000으로 설정했다. 이때, i는 N의 제곱근(가운데 약수)까지만 증가시켜 확인하면 된다.
그리고 가끔씩 문제에서 1이 소수인지 판별해야 하도록 입력 조건이 주어질 수 있는데, 1은 소수가 아니므로 다음 소스코드에 array[1]의 값으로 False를 넣어주면 된다.

# 2부터 n까지 모든 수에 대한 소수 판별
n = 1000

# 처음 모든 수가 소수(True)로 초기화(0, 1 제외) 
array = [True for i in range(n+1)]

# 2부터 n의 제곱근까지 모든 수를 확인
for i in range(2, int(math.sqrt(n)) + 1):

# i가 소수인경우(False를 제외하고 남은 수인 경우)
    if array[i] == True:

# i를 제외한 i의 모든 배수를 지우기
        j = 2
        while i * j <= n:
            array[i * j] = False
            j = j + 1

# 모든 소수 출력
for i in range(2, n+1):
    if array[i]:
        print(i, end= ' ')

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN)으로 사실상 선형 시간에 동작할 정도로 빠르다.
예를 들어, N = 1,000,000일때는 4,000,000정도가 될 것이다.

이처럼 에라토스테네스의 체 알고리즘은 매우 빠르게 동작하기 때문에 다수의 소수를 찾아야 하는 문제에서 자주 사용된다. 다만, 메모리 할당이 많이 필요한데, 알고리즘에서 N의 크기만큼 리스트를 할당하기 때문이다.
예를 들어, N = 1,000,000일때는 2 ~ 1,000,000 까지의 리스트가 필요하다.

따라서, 에라토스테네스의 체를 이용하는 문제의 경우 N < 1,000,000 이내로 주어지는 경우에 사용하자.