분류 전체보기83 [백준 Java] 2015번 수들의 합 4 [Silver II] 수들의 합 4 - 2015 문제 링크 성능 요약 메모리: 35852 KB, 시간: 312 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 1 ≤ N ≤ 200,000 |K| ≤ 2,000,000,000 (20억) $O(N\sqrt N)$ 이하 이어야 한다. 풀이법 ❌ 접근 방법. 완탐 시작점이 0 ~ N-1 , 끝점이 0 ~ N-1로 두고 가능한 모든 부분 배열을 지정한다. → $O(N^2)$ 부분 배열을 순회하며 부분합을 구한다. → $O(N)$ 부분합이 k와 같은지 비교한다. ➡️ 해당 풀이법의 시간 복잡도 : $O(N^3)$ 시간복잡도가 너무 커서 시간이 부족하다. ❌ 접근 방법. 누적합 누적합 배열($S_n)$을 만든다. → $O(N)$ $S_b-S_{.. 2024. 1. 12. [백준 Java] 2004번 조합 0의 개수(정수론) ## 💡문제 ### [Silver II] 조합 0의 개수 - 2004 [문제 링크](https://www.acmicpc.net/problem/2004) #### 성능 요약 메모리: 11564 KB, 시간: 76 ms --- #### [깨진 부분은 여기에서 확인](https://velog.io/@dksek3050/%EB%B0%B1%EC%A4%80-Java-2004%EB%B2%88-%EC%A1%B0%ED%95%A9-0%EC%9D%98-%EA%B0%9C%EC%88%98%EC%A0%95%EC%88%98%EB%A1%A0) ## 🤔접근법 ### 범위 체크 및 시간복잡도 예상 - 0 ≤ m ≤ n ≤ 2,000,000,000 (20억) n ≠ 0 - $O(\sqrt N)$ 또는 $O(logN)$ 이어야 한다. ###.. 2024. 1. 9. [백준 Java] 2247번 실질적 약수(정수론) 💡문제 [Gold V] 실질적 약수 - 2247 문제 링크 성능 요약 메모리: 11588 KB, 시간: 732 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 1 ≤ n ≤ 200,000,000 .. 2억 시간 제한이 2초라 $O(N)$ 도 가능할 거 같다. 풀이법 ❌ 첫번째 접근 방법 . 에라토스테네스의 체 소수 판별 (에라토스테네스의 체) $O(log(logN))$ 소수가 아닌 N에 대해 순회 $O(N)$ → (여기가 이미 188,921,062) 실질적 약수 구하기 SCD(N) $O(\sqrt N)$ ➡️ 해당 풀이법의 시간 복잡도 : $O(N\sqrt N)$이다 ⭕ 두번째 접근 방법 . N까지 x의 배수의 개수 1 ~ N까지 순회 $O(N)$ N 이하의 수에서 어떤 수 i를 .. 2024. 1. 8. [백준 Java] 23888번 등차수열과 쿼리 (정수론) 💡문제 [Gold V] 등차수열과 쿼리 - 23888 문제 링크 성능 요약 메모리: 324788 KB, 시간: 1360 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 1 ≤ $a$ ≤ $10^6$, 0 ≤ $d$ ≤ $10^6$ 1 ≤ $q$ ≤ $10^6$ 1 ≤ $l$ ≤ $r$ ≤ $10^6$ 완탐은 힘들듯 하다. $O(\sqrt N)$ 또는 $O(Nlog{N})$ 이어야 한다. 풀이법 1 $l$ $r$ : $l$ 번째 항부터 $r$ 번째 항까지의 합 → 등차수열 합공식 등차 수열의 합공식을 이용하면 상수 시간으로 구할 수 있을 것이라고 생각했다. 등차수열 합공식 : 항의 개수 * (첫째항 + 끝항) / 2 항의 개수가 n개인 등차 수열의 첫째항을 a, 끝항을 $l$ , 공.. 2024. 1. 8. [백준 Java] 6219번 소수의 자격 (정수론) 💡문제 [Silver III] 소수의 자격 - 6219 문제 링크 성능 요약 메모리: 16376 KB, 시간: 148 ms 🤔접근법 범위 체크 및 시간복잡도 예상 범위 : 1 ≤ A ≤ B ≤ 4,000,000 , B ≤ A + 2,000,000 범위 순회 * 소수 판정 $O(N^2)$은 최대 범위가 2백만이라 어렵다. $O(N\sqrt N)$도 1,000,000 * 1000 이라 어렵다 . $O(Nlog{N})$ 은 될 지 잘 모르겠다. 가능할듯 (대충 N * 8 정도 예상…) $O(\sqrt N)$ 또는 $O(Nlog{N})$ 이어야 한다. 풀이법 🅰️ 첫 번째 접근방법. 완탐 ⭕ 범위 A ~ B 까지 순회하면서 각 숫자들이 소수인지 판별 소수이면 D를 포함하는지 판별 ➡️ 해당 풀이법의 시간 복잡도.. 2024. 1. 7. [백준 Java] 1407번 2로 몇 번 나누어질까(정수론) 💡문제 [Gold IV] 2로 몇 번 나누어질까 - 1407 문제 링크 성능 요약 메모리: 11552 KB, 시간: 76 ms 🌟풀이 범위가 무려 1≤A≤B≤$10^{15}$ 로 엄청나다. 그래서 A ~ B 까지 순회하면서 더할 수는 없다. 1 ~ n까지 소수 x의 배수의 개수를 구하는 방식을 이용하였다. 1 ~ n까지 수들은 소수 x로 몇번 나누어 떨어질까 ? 1부터 20까지 순회하며 각 수를 소인수분해 했을때 2가 몇 번씩 들어가는지 적어보았다. 이를 2가 들어간 횟수만큼 동그라미로 표현하게 되면 아래 사진과 같이 표시되며 오른쪽과 같은 의미를 가질 수 있다. 위를 참고하여 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 .. 2024. 1. 4. 이전 1 ··· 4 5 6 7 8 9 10 ··· 14 다음 반응형
