JAVA - 백준 [BAEK JOON]/기본 수학 2
[백준] 11653번 : 소인수분해 - JAVA [자바]
[백준] 11653번 : 소인수분해 - JAVA [자바]
2021.01.09www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 말 그대로 소인수분해를 하는 문제라 쉽게 풀 수 있을 것이다. 알고리즘 [접근 방법] 소인수분해. 영어로 prime factorization이라고 한다. 아마 대부분 우리나라 교육과정을 다 마치셨다면 기억하실 것이다. 말 그대로 어떤 수를 더이상 쪼개지지 않는 수들의 곱으로 분해하는 것이다. 이를 약간 변형해서 말하자면 어떤 정수 N을 소수들의 곱으로 나타낸다는 것이다. 위 문제에서는 즉, 다음과 같은 구조로 짜면 된다. /* * 임의의 정수 N에 대하여 곱셈으로 분해하면 * 제곱근(√N)을 기준으로 대칭이 된다. * 예로들..
[백준] 9020번 : 골드바흐의 추측 - JAVA [자바]
[백준] 9020번 : 골드바흐의 추측 - JAVA [자바]
2020.05.05https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. www.acmicpc.net 문제 소수를 이용한 문제다. 문제는 그리 어렵지 않으니 한 번 보면 금방 이해될 것이다. ※ 주의할 점 2보다 큰 짝수가 주어질 때..
[백준] 4948번 : 베르트랑 공준 - JAVA [자바]
[백준] 4948번 : 베르트랑 공준 - JAVA [자바]
2020.04.24https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) n이 주어졌을 때, n보다 크고, 2n보 www.acmicpc.net 문제 입력이 주어질 때 N ~ 2N 사이에 몇 개의 소수가 있는지 구하는 문제다. 그리 어려운 문제가 아니니 같이 풀어보도록 하자...
[백준] 1929번 : 소수 구하기 - JAVA [자바]
[백준] 1929번 : 소수 구하기 - JAVA [자바]
2020.04.21https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 이번 문제는 에라토스테네스의 체를 이용하여 풀어보는 정석적인 문제다! 알고리즘 분류에도 에라토스테네스의 체로 분류되어 있다. 4가지 방법을 이용하여 풀이한다. 문제를 들어가보면 알겠지만 알고리즘 분류에도 에라토스테네스의 체로 분류되어있는만큼 해당 알고리즘으로 풀어볼 것이다. 소수를 구하는 방법은 여러가지가 있지만 에라토스테네스의 체가 가장 대중적이면서 알고리즘 효율이 매우 좋은편인 방법이다. 소수를 구하는 방법에 대해 좀 ..
[백준] 2581번 : 소수 - JAVA [자바]
[백준] 2581번 : 소수 - JAVA [자바]
2020.04.21https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 문제 매우 간단한 문제다! 소수를 구하는 알고리즘은 에라토스테네스의 체를 사용할 것이다. 소수를 구하는 빠른 알고리즘을 알고싶다면 아래 글을 먼저 읽고오면 좋을 것 같다. https://st-lab.tistory.com/81 소수를 구하는 알고리즘 - JAVA [자바] 들어가기 전에 소수 [Prime Number] 소수의 정의는 1보다 큰 자연수 중 1 과 그 수 자기 자신만을 약수로 갖는 자연수를 의미한다..
[백준] 1978번 : 소수 찾기 - JAVA [자바]
[백준] 1978번 : 소수 찾기 - JAVA [자바]
2020.04.08https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 드디어 새로운 카테고리의 첫 문제! 소수 찾기다. 당연하겠지만 여기서 말하는 소수는 0.001, 0.235 같은 decimals 가 아닌 1과 자기 자신만을 약수로 갖는 자연수를 의미한다. 2가지 입력방법을 이용하여 풀이한다. Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다. 소수 판별 방법 소수 판별법은 정말 여러가지가 있다. 그 중 대표적인 방법 3가지를 알아보려 한다..