[ BOJ 오답노트 ] 1929 파이썬 : 소수 구하기

2022 01 29

 

1. 틀린 기록

 

 

 

2. 원인 분석

- 시간 초과는 항상 힘들게 한다~! 시간 초과 코드로 일반적인 소수 구하듯이 주어진 범위 내의 숫자들을 하나씩 검토해서 출력했다.

- for문 안에 while문까지 있다보니까 시간 초과 판정이 난 것 같다.

- 도저히 해결하는 방법이 생각이 안나서 문제의 서브 주제를 봤더니 '에라토스테네스의 체'라는 알고리즘으로 풀어야 한다고 써있었다.

 

 

 

3. 해결

- 에라토스테네스의 체 : 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2부터 N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식

- 하나씩 다 검토하면서 제거한다고 하면 시간 복잡도가 크다고 생각할 수 있지만, 2부터 배수들을 다 지워나가면서 점점 더 검토할 숫자들이 줄어들어서 O(N^1/2)의 시간 복잡도를 가진다.

 

- N+1 크기의 리스트를 만들고 모든 요소를 False로 초기화한다. 이때, False는 지워지지 않은 값, True는 이미 지워진 값을 의미한다.

- 0과 1은 소수가 아니므로 미리 True 값으로 만들어주고, 이후 2부터 N까지 배열 요소 하나씩을 검토한다.

- 배열 요소가 True라면 이미 지워진 값이므로 넘어간다. 한편, False라면 그 수에서 비롯된 모든 배수를 다 True값으로 만들어서 두번 다시 검토하지 않게 해준다.

 

 

 

4. 배운 점

- 에라토스테네스의 체에 대해서 처음 알게 되었는데 굉장히 속도가 빠른 알고리즘인 것을 알게되었다.

- 오히려 하나씩 비교하는 소수 판정 알고리즘보다 코드도 더 깔끔한 것 같아서 앞으로 종종 사용할 알고리즘인 것 같다.