소수문제
소수문제는 알고리즘 문제에서 가장 단골로 등장하는 문제중 하나일 것이다. 소수는 1이외에 자기 자신으로만 나눠지는 숫자인데, 단순히 어떤 숫자가 소수이냐로 판별하는데 그치는 것이 아니라, 소수를 이용한 다른 응용문제들로 이어진다. (예를들어 소수의 갯수가 몇개이냐 하는...)
이번 문제가 바로 정석적인 소수 갯수찾기 문제이다.
문제
기록
- 제한 조건만 보아도 효율성에 관련된 문제인 것을 알 수 있다. 소수를 찾는것에 대한 가장 기본적인 접근으로 보자면, 어떤 수를 2부터 그 수까지 차례대로 올라가며 나눠지는 코드를 짜면 될 것이다.
function solution(n){
let result = 0;
for(let i = 2; i<=n; i++){
let count = 0;
for(let j = 2; j<=i; j++){
if(i % j === 0) count++
}
count === 1 ? result ++ : null;
}
return result;
}-
해당 방법은 직관적으로 파악이 쉬운 코드이다. 하지만 컴퓨팅사고의 가장 중요한 점은, 인간의 로직과 똑같이 로직을 적용하면 컴퓨터에겐 좋은 로직은 아니라는 것이다. 언제나 극단적인 상황도 생각해야하는데, 해당 문제처럼 case가 백만인 경우에는 for문을 중첩시킨 저 로직은 시간복잡도가 기하급수적으로 늘어나게된다.
(당연히 효율성 테스트는 실패한다)
이를 해결하기 위해 여러 방법을 적용해 볼 수 있겠는데, 소수의 원리를 이용하는 것들이다. -
제곱근 활용
어떤수 n이 어떤수의 배수라는 얘기는, n = ab 로 나타낼 수 있다. 순서가 중요하지 않는 a,b조합을 나열한다면, a<=b 일때 a의 가장 큰 수는 √n 이라고 할 수 있다.
ex) n = 16 일때 (a,b) 는 [(1,6),(2,8) (4,4)] , a가 4일때 가장 큰 수
그러므로 2부터 n까지 확인하지 않아도 2부터 √n까지만 확인하면 되는 것이다. -
아라토스테네스의 체
이것만으로 부족할 수 있다. 만약 어떤 수가 일정 수 이상 커지지 않는다면 위의 결과만으로도 순회를 반절이하까지 줄일 수 있지만, 그렇다고 해도 백만개의 케이스를 이중중첩으로 순회하게 된다면 여전히 시간복잡도는 상당하다.(3번을 적용한 코드 또한 효율성 테스트는 실패하였다)
결국 소수가 아닌 수는 어떤 수의 배수다. 아라토스테네스의 체는 이 점을 활용한 로직이다. 2부터 시작해서 그 배수를 줄여나간다면 결국 소수만 남게된다는 로직이다. 소수의 갯수를 구하는 문제에서는 최적의 방법이 될 수 있다.
이 방법은 위의 제곱근 활용의 방법을 적용할 수 있다. 왜냐하면 2~n까지의 수에서 √n까지 배수를 걸러냈다면, 그 아랫수 배수들은 이미 다 걸려졌고, 그 이상은 3번의 원리에 의해서 걸러낼 필요가 없기 때문이다.
- 이번 문제를 풀며 느낀 점은, 역시나 좋은 코드는 꼭 사람의 로직과 똑같이 따라가지 않는다는 것이다. 컴퓨터가 가장 빠르고 효율적이게 해결할 수 있는 방법을 생각해야한다. 그러기 위해서는 효율성을 저해하는 방법대로 생각하는 습관을 없애기 위해 노력해야할 것 같다.
(이중 for문 경계하기, 쓸데없는 배열조작 및 할당 줄이기, 수학적 원리를 사용하기 등등)
그렇게 만들어진 해답은 아래와 같다.
내풀이
function solution(n) {
let result = new Array(n+1)//실제 체 모양을 구현하고자 한다
result.fill(1)
result.fill(0,0,2) //fill이 동적 할당보다 속도가 빠르다.
let sqrt = Math.sqrt(result.length);
for(let i= 2; i<sqrt; i++){
if(result[i]){
for(let j = i * 2; j<result.length; j+=i){
result[j]= 0; //배수는 모두 0으로 바꾼다.
}
}
}
result = result.filter(el=>el)//남은 1은 결국 소수의 갯수이다.
return result.length
}