[TIL][240731] 약수, 소수, 시간복잡도 그리고 에라토스테네스의 체

어떤 문제가 있었나?

오늘의 알고리즘 코드카타 문제: [프로그래머스] Lv.1 기사단원의 무기 

알고리즘 문제를 풀면서 처음으로 시간초과 오답을 경험했다. 최근 시간 복잡도를 배워서 그런지 연산이 비효율적이라 판단했다. 아래 코드는 number를 range 함수로 i로 반복하고, i의 약수의 개수를 세는 코드이다.

def solution(number, limit, power):
    attacks = []
    for i in range(1, number+1):
        count = 0
        for j in range(1, i+1):
            if i % j == 0: 
                count += 1
        attacks.append(count)
    for i in range(number):
        if attacks[i] > limit:
            attacks[i] = power
            
    return sum(attacks)

시간복잡도가 늘어난 이유를 분석해 보자면  첫 번째는 이중 반복문을 사용한 것이고, 두 번째는 약수를 구하는 알고리즘이 비효율적일 것이다. 로직 상 이중 반복문은 쓸 수밖에 없으니 약수를 구하는 알고리즘을 수정해 봤다.

---

무엇을 시도했나?

예전 소수 관련 문제를 풀면서 소수 판별에 여러 가지 방법이 있다는 사실을 알게 되었다.(가장 쉬운 방법만 챙기고 넘어갔지만...) 소수 판별 알고리즘은 약수를 구하는 알고리즘에서 나왔기에(약수를 구하는데  여기에서 힌트를 얻고 소수 판별 알고리즘을 찾아봤다. 

소수 판별법에는 O(N), O(N**0.5), O(n*log(logN))이 있다. 크게 보면 다 O(N)인 것 같아 보인다. 복잡해 보이는 시간복잡도 말고 중간의 제곱근을 이용해서 풀어봤다.

---

어떻게 해결됐는가?

약수를 판단할 때 제곱근을 기준으로 대칭을 이루기 때문에 모두 반복할 필요가 없었다. 따라서 제곱근이 나누어 떨어지는지만 확인하면 앞서 풀었던 코드보다는 효율적으로 반복할 수 있었다.

def solution(number, limit, power):
    attacks = []
    for i in range(1, number + 1):
        count = 0
        root = int(i**(1/2))
        for j in range(1, root+1):
            if i % j == 0:
                if i == j**2:
                    count += 1
                else:
                    count += 2
        attacks.append(count)
    for i in range(number):
        if attacks[i] > limit:
            attacks[i] = power

    return sum(attacks)

---

새로 알게 된 점은 무엇인가?

시간 복잡도 O(N**0.5), O(n*log(logN))도 O(N)이라고 볼 수 있지만 코드의 효율을 조금이라도 올릴 수 있다는 사실을 알게 되었다. 이번 기회에 소수를 판별하는 여러 가지 방법과 시간 복잡도를 알아봤다.

 

O(N): 소인수분해를 이용한 소수 판별(Complete Prime Factorization)

가장 기본적이지만 느린 방법으로 입력된 숫자를 range() 함수로 반복하여 나머지 연산 결과가 0인지 아닌지 조건문을 통해 판별한다.

m=0
flag=0
n = 11
if(n == 1):
  flag = 1
  print("Not Prime")
for i in range(2,n):
  if(n % i == 0):
      print("Not Prime")
      flag=1
      break  
  
if (flag==0):
  print("Prime")

이때 시간 복잡도는 숫자가 소수인 경우 N개의 숫자를 탐색하므로 O(N)이다.

 

O(N/2): 소인수분해를 이용한 소수 판별(Half Factorization)

위의 소인수분해를 이용한 소수 판별은 오늘 풀었던 문제처럼 큰 숫자를 받을 때 효율적이지 않다. 사실 끝가지 반복하지 않고 소수를 판별할 수 있다. 입력된 숫자를 2로 나누어 인수를 절반으로 만든다면 조금 더 효율적으로 소수를 판별할 수 있다.

m=0
flag=0
n = 11
if(n == 1):
  flag = 1
  print("Not Prime")
for i in range(2, n//2 + 1):
  if(n % i == 0):
      print("Not Prime")
      flag=1
      break  
  
if (flag==0):
  print("Prime")

이 때 시간복잡도는 위와 마찬가지로 O(N)을 유지한다. 하지만 절반만 반복하기에 O(N/2)라고 할 수도 있다.

 

O(N**0.5) 제곱근을 이용한 소수 판별

소인수분해를 이용한 방법으론 반복 횟수를 절반이나 줄였음에도 불구하고 시간복잡도의 변화는 없었다. 시간 복잡도를 줄이기 위해 나온 또 다른 방법이 제곱근을 이용한 소수 판별이다. 제곱수인 36과 제곱수가 아닌 수 40의 인수를 보면 아래와 같다.

제곱근 인수가 중앙에 배치되고 나머지 인수들이 대칭된 것을 확인할 수 있다. 즉, 주어진 수의 제곱근 위에는 제곱근이 완전 제곱이든 아니든 항상 적어도 하나의 인수가 있을 것이다. 따라서 제곱근 위나 아래에 있는 인수를 찾고, 인수가 있다면 소수가 아니게 된다.

m=0
flag=0
n = 11
if(n == 1):
  flag = 1
  print("Not Prime")
for i in range(2, n**(1//2) + 1):
  if(n % i == 0):
      print("Not Prime")
      flag=1
      break  
  
if (flag==0):
  print("Prime")

이 방법의 시간 복잡도는 N**0.5개의 숫자만 탐색하기 때문에 O(N**0.5)가 된다. 이것 또한 O(N)에 들어가야 할 범주 같지만 조금이라도 효율적으로 보였다. 아래는 O(logN)의 비교 그래프를 가져와봤다. N이 충분히 큰 값이라면 시간 복잡도는 O(logN)이 O(N**0.5) 보다 효율적이라는 것을 확인할 수 있다.

https://velog.io/@nathan29849/Python-Algorithm-class-log-n-%EA%B3%BC-n-%EB%B9%84%EA%B5%90

 

에라토스테네스의 체

한 개의 숫자가 소수인지 판별하는 방법으론 위의 3가지 방법으로 충분하다. 하지만 특정 범위의 소수의 개수를 구하거나, 소수의 리스트를 얻기 위해서는 결국 N만큼 곱해진 시간복잡도를 가질 것이다. 이럴 때 쓰이는 알고리즘이 에라토스테네스의 체(Sieve of Eratosthenes)이다.

이 알고리즘은 단순한 소수 판별에서 사용하게 된다면 오히려 시간복잡도가 올라가지만 범위 내 소수를 찾을 때 효과적이다. 에라토스테네스의 체의 방법은 아래와 같다.

1. 2부터 N까지 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다)
4. 더 이상 반복할 수 없을 때까지 2,3번의 과정을 반복한다.

위의 과정을 거쳐 배열에 남은 숫자들이 해당 범위 내 소수들이다. 이 방법을 사용하면 모든 수를 반복하지 않아도 돼서 시간복잡도를 효율적으로 줄일 수 있다.

import math

n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별
# 처음엔 모든 수가 소수(True)인 것으로 초기화(0, 1은 제외)
array = [True for i in range(n+1)]

# 에라토스테네스의 체 알고리즘 수행
# 2부터 n의 제곱근까지의 모든 수를 확인하며
for i in range(2, int(math.sqrt(n))+1):
	if array[i] == True: # i가 소수인 경우(남은 수 인 경우)
    	# i를 제외한 i의 모든 배수를 지우기
        j = 2
        while i * j <= n:
        	array[i*j] = False
            j += 1
# 모든 소수 출력
for i in range(2, n+1):
	if array[i]:
    	print(i, end=' ')

이 알고리즘의 시간복잡도는 O(N*log logN)...? 라고 한다.

---

무엇을 느꼈고 내일은 무엇을 할까?

처음으로 시간 복잡도를 고려하여 문제를 풀게 되었다. 예전 같았으면 포기했을 법한데, 어렵지만 조금 더 파고 들어가 학습해 보니 기존에 배웠던 것에 대해 살을 붙이는 느낌이 어떤 것인지 조금이나마 알게 되었다. 내일은 그래프 순회에 대해 복습하고 정리할 예정이다.