Start
성능 개선을 하러 가보겠습니다.
CountNonDivisible 문제
에라토스테네스의 체 방법을 통해 소수를 구하는 방법을 알고 있었는데, 까먹었다...
1. 소수를 찾고
2. 배열에서 각 요소마다의 개수를 찾고
3. 1이나 소수일 경우 전체 요소의 개수에서 1과 소수의 개수를 뺀다.
4. 그렇지 않을 경우 배열에서 나눠본다.
했는데, 아래와 같은 결과가 나왔다.
시간복잡도가 N^2인데 이전 풀이도 N^2였는데, 좀 더 안 좋은 풀이인가보다..
소수가 아닐 경우 전체 배열을 돌면서 나눠보는 방법 대신 소수가 아닌 수의 공약수를 구해서 배열에 존재할 경우 빼도록 구했다.
공약수를 구하는 방식은 이전 lesson이었던 lesson 10에서의 방법을 통해 구했다.
성능은 괜찮아진 것 같은데, 런타임 에러가 발생했다. 인덱스를 넘어섰다는데 찾아보겠다..
초반에 소수를 구했는데, 50,000까지만 소수를 구해서 생긴 문제였다. 입력 범위인 100,000까지 소수를 구하도록 변경하였다.
CountSemiprimes 문제
prime 숫자 두 개의 곱으로 이루어진 수를 semi_prime이라고 한다.
두 개의 배열 P, Q가 주어지고 P[K] ~ Q[K] 사이에 semi_prime이 몇 개 있는지 구한다.
배열의 요소는 1부터 50,000까지로 구성된다.
1. 50,000까지의 소수를 구한다.
2. 구한 소수를 바탕으로 50,000까지의 semi_prime을 구한다.
-> semi_prime을 구할 때는 공약수 구하기 알고리즘을 이용하는데, 나눈 수와 나눠진 수가 각각 소수인지 1번에서 구한 것으로 체크한다.
-> 이 semi_prime을 구할 때 해당 semi_prime까지 몇 개의 semi_prime이 있었는지 구한다.
3. 0부터 P, Q 크기까지 차례대로 각 범위 안에 몇 개의 semi_prime이 있는지 구한다.
여기서 잠깐 에라토스테네스의 체를 정리하고 가자면..!
아래와 같이 구하는 방식으로 2부터 N까지 소수가 아닌 수를 배제하는 방식으로 진행한다.
2는 소수이기 때문에 패스하고 2의 배수를 모두 지운다.
3은 소수이기 때문에 패스하고 3의 배수를 모두 지운다.
4는 2의 배수로 지워졌다.
5는 지워지지 않았으므로 소수이기 때문에 패스하고 5의 배수를 모두 지운다.
6은 지워졌고 7은 소수이기 때문에 패스하고 7의 배수를 모두 지운다.
이렇게 쭉쭉 진행하다보면
소수는 visited에서 false로 남게 된다.
소수를 구하는 가장 빠르고 좋은 방법이기 때문에.. 되도록이면 잊지 말고 기억하자..!
그리고 제곱근까지의 공약수를 구해서 문제를 풀고 있는데! (아래와 같은 느낌으로)
제곱근까지만 구하기 때문에 시간 복잡도가 굉장히 줄어들게 된다.
공약수가 필요한 경우 시간복잡도가 효율적으로 바뀌기 때문에 이 방법을 되도록이면 기억해두자..!
ChocolatesByNumbers 문제
일단 문제 파악 시간이 줄어서 스스로 너무너무 기특하다..증말..
입력값(10억이요..?)이 너무 큰데, 당장 뾰족한 수가 떠오르지 않아 일단 성능은 포기하고 풀었다.
좀 더 헤매도 좋긴 한데, 호제법이 뭔지 떠올리면서 고민하는 게 좋을 것 같아서 찾아보았다. (나무위키..)
위와 같이 구하는 것이 호제법으로 알고있다.
그렇다면 구하는 부분과 호제법과의 상관관계를 생각해보자..
'코딩테스트' 카테고리의 다른 글
| [2023-02-13] (0) | 2023.02.13 |
|---|---|
| [2023-02-09] (0) | 2023.02.09 |
| [2023-01-24] (0) | 2023.01.24 |
| [2023-01-21] (0) | 2023.01.21 |
| [2023-01-20] (0) | 2023.01.20 |