매일매일 알고리즘 공부

package quiz; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; /** * 괄호. * 괄호 문자열 = '(' , ')' 만으로 구성되는 문자열이다. * 괄호 모양이 바른 것 = 올바른 괄호 문자열 (vps) * 한 쌍의 괄호 기호로된 문자열 "()" : 기본 vps * x가 vps 라면 "(x)" 문자열도 vps 가 된다. * 그리고 두 vps x와 y 를 접합 시킨 문자열 xy 도 vps 가 된다. (vps + vps => vps) * 입력으로 주어진 괄호 문자열이 vps 인가 판단하는 yes, no 프로그램을 만드시오. */ publ..

package quiz; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * 골드바흐 파티션 */ public class Main { static int[] primeArr = new int[1000001]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int testCase = Integer.parseInt(br.readLine()); makingPrimeArr(); for ( int i..

package quiz; import java.io.BufferedReader; import java.io.InputStreamReader; /** * 4948번 풀이 - 베르트랑 공준 * 베르트랑 공준은 임의의 자연수 n에 대하여, * n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. * 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. * 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) * * 자연수 n이 주어졌을 때, n보다 크고 2n보다 작거나 같은 소수의 개수를 구하여라. * **/ public class _4948 { public static void main(..

💡 👍🏻 [에라토스테네스의 체] 는 고대 그리스 수학자인 에라토스테네스가 만들어낸 소수를 판별하는 알고리즘이다. 마치 체를 가지고 수를 걸러내는 것 같아, '에라토스테네스의 채' 라고 부른다. 소수란 약수가 오로지 1인 수이다. 즉, 1을 제외한 수의 배수가 되는 수는 소수가 아니다. 소수를 대량으로 빠르고 정확하게 구할 때 이용한다. 지워지지 않은 수들이 소수이다. 에라토스테네스의 원리 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고 이후 하나 씩 지워가는 방법을 이용한다. 2부터 시작해서 특정 수의 배수에 해당되는 수를 모두 지운다. 2부터 시작해서 남은 수를 모두 출력한다. 🛠 예를 들어, 2부터 n까지의 수 중에서 소수를 구한다고 했을 때, 2는 소수니까 그대로 두고, n까지 순차..

package baekjoon; import java.math.BigInteger; import java.util.Scanner; public class _1929 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long m = sc.nextLong(); long n = sc.nextLong(); sc.close(); findSosu(m,n); } public static void findSosu(long m, long n) { for ( long i = m; i

계속 틀리네... 시간초과..... package quiz; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; /** * 다음 소수 * 정수 n이 주어졌을 때, n보다 크거나 같은 소수 중에 가장 작은 소수를 찾는 프로그램을 작성하시오. * @author Back */ public class _ { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t..

package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; /** * 가로수 * - 같은 간격으로 가로수 추가 심기. * - 단, 예산은 가장 적은 수의 나무를 심고 싶다. * 거리 = 기준점으로부터 떨어지는 거리. 모두 양의 정수이다. * * 1. 심어진 가로수의 위치가 주어질 때, * 모든 가로수가 같은 간격으로 심어지도록 하는 가로수의 최소수를 구하여라. * * @author Back * */ public class _2485 { public static void main(String[] args) throws Num..

package quiz; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * 분수 합 * - 분서 a/b는 분자가 a, 분모가 b인 분수이다. (a,b는 모두 자연수) * - 두 분수의 합 또한 분수로 표현할 수 있다. * - 두 분수가 주어졌을 때, 그 합을 기약 분수의 형태로 구하는 프로그램을 작성하시오. * (기약분수 : 더 이상 약분되지 않는 분수를 의미한다.) * * 출력 : 첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 두고 출력한다. */ public class _1735..

첫 번째 문제 : 1934번 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * 두 자연수 a,b에 대하여, a의 배수이면서 b의 배수인 자연수를 * a와 b의 공배수라고 한다. * * 이 공배수 중에서 가장 작은 공배수를 최소 공배수라고 한다. * 두 자연수가 주어졌을 때, a와b의 최소공배수를 구하시오. * @author Back * */ public class _1934 { public static void main(String[] args) throws NumberFormatExce..

유클리드 호제법 (GCD) 💡 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나이다. 호제법 = 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다. 명시적으로 기술된 알고리즘 중 가장 오래되었다고 알려져 있다. 원리 1️⃣ 2개의 자연수 a,b 에 대하여 a를 b로 나눈 나머지가 r이면 (단, a>b) , a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 2️⃣ 이 성질을 이용해 이번에는 b를 r로 나눈 나머지 r2 를 구하고, 다시 r을 r2 로 나눈 나머지를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수인 것이다. 접근방법 1️⃣ 반복문을 이용한 방법 2️⃣ 재귀를 이용한 방법 int GCD(int a, ..