Algorithm45 [백준 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. [알고리즘 정리] Binary Search ( 이분 탐색 ) - O(logN), 탐색알고리즘 Binary Search (이분탐색) 이란? "정렬"되어 있는 배열에서 특정 값의 위치를 찾는 탐색알고리즘이다. 탐색하는 배열을 둘로 나누고 찾고자하는 값이 존재하는 영역만 탐색하기 때문에 전체를 탐색하는 경우보다 당연히 빠르게 찾을 수 있다. 더보기 백준 문제 1. 수 찾기 https://www.acmicpc.net/problem/1920 과정 내가 찾고자하는 값을 '타겟'이라고 하자. 이분탐색은 주로 배열에서 타겟의 위치(인덱스)를 찾고자 할 때 많이 사용된다. 1. 탐색할 배열을 정렬한다. 2. 탐색할 영역의 중앙값( = (시작점 + 끝점)/2)이 타겟과 비교한다. 2-1. 중앙값이 타겟과 같다면 중앙값의 위치를 반환하고 탐색을 종료한다. 2-2. 타겟이 중앙값보다 작다면 다음엔 중앙값을 기준으로 .. 2023. 8. 14. [백준 Java] 17071번 숨바꼭질5 (BFS) [Platinum V] 숨바꼭질 5 - 17071 문제 링크 성능 요약 메모리: 89244 KB, 시간: 248 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 문제 설명 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위.. 2023. 8. 10. 이전 1 2 3 4 5 6 7 8 다음 반응형
