99클럽 코테 스터디 1일차 TIL - 백준 1929

문제: https://www.acmicpc.net/problem/1929

오늘 공부한 내용 - 소수 알고리즘, 에라토스테네스의 체

 

소수란, 1과 자기 자신만을 약수로 가지는 수를 의미한다.

이를 활용하여 일반적인 소수 구하는 알고리즘을 짜보면 다음과 같다.

 

소수 판별 알고리즘 

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

 

그러나 해당 알고리즘을 사용하면 시간초과가 발생한다.

 

m, n = map(int, input().split())
arr = [i for i in range(m, n+1)]

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

for num in arr:
  if isPrimeNumber(num):
    print(num)

 

문제 설명에서 확인할 수 있듯이, m과 n이하의 모든 소수를 출력해야하는데 M, N의 범위가 모두 10^6 이하이므로,

 

m과 n이하에 있는 범위에 있는 모든 수를 위 반복문 알고리즘을 통해 판별하게 되면

위 풀이는 시간 복잡도가 O(n^2)이 되면서 시간초과가 발생한다. (코딩테스트에서 통상적으로 1초 = 10^8을 기준으로 하여 시간복잡도 계산)

 

따라서 시간복잡도를 줄여줄 알고리즘을 사용해야하는데, 이전에 "에라토스테네스의 체" 라는 시간복잡도가 개선된 소수 판별 알고리즘을 학습했지만 복습 겸 해당 알고리즘을 다시 살펴보았다.

개선된 소수 판별 알고리즘 - 에라토스테네스의 체 (시간복잡도: O(NloglogN))

 

에라토스테네스의 체 알고리즘은, 아직 처리되지 않은 가장 작은 수를 찾아 그 수를 제외한 배수를 차례대로 제거함으로써 소수를 찾는 알고리즘이다.

 

import math

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

# 에라토스테네스의 체 알고리즘 
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    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=' ')

 

*출처: https://github.com/ndb796/python-for-coding-test/blob/master/20/2.py

 

1) 먼저 n까지의 수들 중에 소수만 찾는다고 할 경우, n만큼 크기의 배열을 모두 True값으로 초기화하여 소수라고 가정한다.

2) 그리고 2부터 n까지의 제곱근에 해당하는 자연수까지 루프를 돌며, 처리되지 않은(True) 수부터 시작하여 해당 수의 배수를 모두 소수가 아닌것으로 처리한다.

- 제곱근까지만 처리하는 이유는, 이미 앞 루프의 배수를 지우는 과정에서 처리가 되었기 때문에 그 뒤 수까지 루프를 돌 필요가 없다.

3) 최종적으로 True인 수들은 배수 처리가 안되어 1과 자기 자신만을 약수로 가지는 수, 즉 소수 이므로 해당 값들을 출력한다.

 

따라서 해당 알고리즘을 활용하여 다시 문제를 풀어보면

import math

m, n = map(int, input().split())
arr = [True] * (n+1) # 소수인지 여부를 담을 배열 -> 처음엔 다 소수로 가정
arr[1] = False

for i in range(2, int(math.sqrt(n))+1):   # int(n**0.5) + 1
	if arr[i]:
		# i를 제외한 i의 모든 배수에 False 표시 (무언가의 배수이면 소수가 아님)
		j = 2
		while (i*j) <= n:
			arr[i*j] = False
			j += 1

for i in range(m, n+1): # 모든 소수 출력
	if arr[i]:   # 위 로직을 거쳐서 True인거라는거는 소수라는 의미임
		print(i)

 

위와같이 풀이할 수 있다.

arr[1] = False로 지정한 이유는, m과 n이 자연수이므로 1이 input값으로 들어오는 경우가 있기 때문에, 예외처리를 위함이다.

False 처리하지 않으면 2부터 루프를 도는 과정에서 제외되면서 계속 소수로 남기때문에 초기에 1은 소수가 아닌 것으로 초기화했다. 

 

오늘의 회고

- 금일 정기 스터디의 깜짝 문제를 통해 Python의 Counter 라이브러리의 most_common() 메서드에 대해 알 수 있었다.
해당 메소드는 (원소 값, 원소 빈도 수) 튜플 리스트를 빈도가 높은 순서대로 반환하며, 인자로 n을 넣게되면 빈도수 순위가 n까지인 리스트를 반환한다.

- 하루에 자소서만 5개가 휘몰아쳐서 알고리즘 공부를 많이 못했다. 내일은 더 많이해야지..