TIL 23-05-21 백준 - 소수 구하기 (에라토스테네스의 체)

1.백준 알고리즘 - 소구 구하기 

 문제점

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

1929번: 소수 구하기

 시도해 본 것들

set을 활용한 remove 사용하기 

M, N = map(int, input().split())
# M=1인 경우 1이 출력되는 이슈 방지용 max() 사용
num_set = set([x for x in range(max(2, M), N + 1)])
for num in list(num_set):
    # 집합에 num이 존재하는지 체크
    if num in num_set:
        # num의 제곱근까지만 for문 진행
        for n in range(2, int(num**0.5) + 1):
            if num % n == 0:
                try:
                    # set의 remove이므로 시간복잡도 o(1)
                    num_set.remove(num)
                    break
                except KeyError:
                    break
    # 해시 테이블로 바뀐 순서 재정렬
print(*sorted(num_set), sep="\n")

set의 remove가 o(1)의 시간복잡도를 가지는 것과 

int(num**0.5) + 1) 으로 num의 제곱근까지만 for문을 진행하면서 시간복잡도 개선

사실상 set의 remove하나에 기대어 작성한 코드로 솔직히 시간 초과로 터질 줄 알았다. 

 

에라토스테네스의 체 구현하기

M, N = map(int, input().split())
# 0과 1을 False로 설정
num_list = [False] * 2 + [True] * N
# int(N**0.5) +1으로 N의 제곱근까지 for문 설정
for num in range(2, int(N**0.5) + 1):
    # num_list[num]이 True라면
    if num_list[num]:
        # num의 배수 찾기
        for n in range(num + num, N + 1, num):
            # False로 소수 아님 처리
            num_list[n] = False
# 여러줄 출력을 위해 *, sep='\n' 사용
print(*[i for i in range(M, N + 1) if num_list[i]], sep="\n")

구조 자체는 어렵지 않았는데 코드로 만드는 과정이 어려웠다. 

 num_list,N,num,n같은 식으로 변수 선언을 해서 하나씩 빠진 부분을 수정하는 게 어려웠다. 

확실히 첫번째 for문의 범위부터 차이가 나서 시간복잡도가 크게 개선됐다. 

 

 알게 된 점

다른 부분이 크게 효율적이지 않았는데 코드를 통과하게 만든 시간복잡도 o(1)인 set의 힘을 느꼈다. 

소수 문제를 몇 번 풀면서 에라토스테네스의 체를 알게 됐지만, 이제 처음 사용해보면서 이런 개념을 미리 접할 수 있도록 알고리즘의 비중을 둔것을 다행이라고 생각한다.