PS/BOJ
BOJ 6588 골드바흐의 추측 [Java]
BOJ 6588 골드바흐의 추측 1. 문제 링크 https://www.acmicpc.net/problem/6588 2. 문제 해설 true이면 소수이고, false면 소수가 아닌 isPrime 배열을 만든다. 테스트 케이스의 범위가 6이상 1000000이하이므로 크기는 1000001로 지정해준다. 일단 isPrime 배열의 원소를 전부 true로 초기화해주고, 그 후 에라토스테네스의 체를 이용하여 소수가 아닌 수들은 false로 바꿔준다. 이제 골드바흐의 추측이 가능한지 아닌지를 판단해주는 impossible 함수에 대해 설명해보겠다. impossible 함수는 n을 매개변수로 받고, n 이하의 짝수들을 전부 탐색하면서 두 짝수 소수의 합으로 나타낼 수 있으면 앞 쪽 소수를 반환한다. 두 짝수 소수의 합..
BOJ 1929 소수 구하기 [Java]
BOJ 1929 소수 구하기 1. 문제 링크 https://www.acmicpc.net/problem/1929 2. 문제 해설 주어지는 두 수의 범위가 1부터 1,000,000 사이이다. 1부터 1,000,000까지 모두 나눠보는 방식은 시간 제한에 걸리기도 하고 굉장히 비효율적이다. 주어진 범위 내에서 소수 판별을 하는 가장 좋은 방법으로 '에라토스테네스의 체' 라는 방식이 있다. 예를 들어 1부터 100까지의 수 중에서 소수를 판별한다고 할 때, 에라토스테네스의 체가 어떻게 동작하는지 살펴보자. 일단 소수도 합성수도 아닌 1을 제외한다. 2를 제외한 범위 내의 2의 배수를 전부 제외한다. 3을 제외한 범위 내의 3의 배수를 전부 제외한다. 4의 배수는 이미 2의 배수를 제외하는 과정에서..
BOJ 11576 Base Conversion [Java]
BOJ 11576 Base Conversion 1. 문제 링크 https://www.acmicpc.net/problem/11576 2. 문제 해설 a진법의 수를 b진법의 수로 바꿔줘야하는 문제이다. a진법의 수를 10진수로 바꿔주고 그 10진수를 b진법의 수로 바꿔주는 방식으로 해결했다. 아래 코드에서 sum은 a진법의 수를 뜻하는 10진수이고, 그 10진수를 b로 나누어주면서 나머지를 스택에 저장하였다. 입력된 수가 0일 경우에는 0을 바로 출력하게 설정하였다. 3. 코드 보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedR..
BOJ 2089 -2진수 [Java]
BOJ 2089 -2진수 1. 문제 링크 https://www.acmicpc.net/problem/2089 2. 문제 해설 -2진수도 2진수와 같이 결국 1과 0으로만 표현해야한다. 10진수를 2진수로 바꿔줄 때와 비슷하게 10진수를 -2로 나누어주며 과정이 진행된다. -2로 나누어주면 나머지가 0 혹은 -1이 나오는데 0의 경우는 2진수와 동일하게 처리가 가능하지만, -1의 경우는 다른 방식이 필요하다. 나머지가 -1인 경우를 어떻게 처리하는지 예시를 들어보겠다. 7을 -2로 나누는 경우를 생각해보자. 7 / (-2) = (-2) x (3) - 1 이다. 이것을 다르게 표현하면, 7 / (-2) = (-2) x (4) + 1 이다. 즉, 나머지가 -1인 경우에는 나머지를 1로 바꿔주고 몫을 1 더해주면..
BOJ 1978 소수 찾기 [Java]
BOJ 1978 소수 찾기 1. 문제 링크 https://www.acmicpc.net/problem/1978 2. 문제 해설 소수인지 아닌지 판별해야하는 수가 1000이하이고 100개 이하로 주어진다. 주어진 조건의 범위가 작기에 1부터 1000까지 전부 다 나눠보는 방식으로 하여도 충분히 시간 제한을 만족한다. 입력 받은 수가 소수인지 판별하는 isPrime 메소드를 만들었다. cnt는 소수의 갯수를 의미한다. 주어진 n개의 수에 isPrime 메소드를 이용하여 소수인지 판별하고, 소수라면 cnt를 1 더해준다. 최종적으로 cnt를 출력한다. 3. 코드 보기 import java.io.*; import java.util.*; public class Main { static boolean isPrime(..