본문 바로가기

Algorithm234

[백준] 9020번 : 골드바흐의 추측 - Java https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 주의점 2보다 큰 짝수에 대한 소수의 합 구하기 소수의 합이 여러 개일 때, 두 소수의 차이가 작은 경우 출력 두 소수 중 작은 수부터 출력 알고리즘 에라토스테네스의 체 활용 짝수 n에 대한 두 소수 구하기 + 두 소수의 차가 작은 경우 출력 예시 n = 14 n = p + q (p와 q는 소수) 14 = 7 + 7 14 = 3 + 11 ➡ 두 소수의 차가 작은 7 7 출력해야.. 2022. 3. 30.
[백준] 4948번 : 베르트랑 공준 - Java https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 참고 유형 https://unknownomad.tistory.com/147 [백준] 1978번 : 소수 찾기 - Java https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 주의점 소수 1과.. unk.. 2022. 3. 29.
[백준] 1929번 : 소수 구하기 - Java https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 참고 유형 https://unknownomad.tistory.com/147 [백준] 1978번 : 소수 찾기 - Java https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 주의점 소수 1과.. unknownomad.tistory.com 구.. 2022. 3. 29.
[백준] 11653번 : 소인수분해 - Java https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 참고 유형 https://unknownomad.tistory.com/147 [백준] 1978번 : 소수 찾기 - Java https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 주의점 소수 1과.. unknownomad.tistory.com 소인수분해 어떤 수를 소수인 인수로 분해하는 것 알고리즘 1. 반복문의 범위 : √N 어떤 .. 2022. 3. 28.
[백준] 2581번 : 소수 - Java https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 참고 유형 https://unknownomad.tistory.com/147 [백준] 1978번 : 소수 찾기 - Java https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 주의점 소수 1과.. unknownomad.t.. 2022. 3. 28.
[백준] 1978번 : 소수 찾기 - Java https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 주의점 소수 1과 자기 자신만을 약수로 가지는 자연수 1은 소수가 아님 ➡ 예외 처리 필수 해당 범위 : 2 ~ (N - 1) 알고리즘 : 소수 찾기 1. 기본 판별법 1과 자기 자신만을 약수로 가짐 ➡ 2부터 판별하려는 수 직전까지 하나씩 나누기 나눠 떨어지는 수 有 소수 O 나눠 떨어지는 수 無 소수 X 2. 제곱근 판별법 Number = A X B 의 합성수 (Number = A X B) 1 ≤ A, B ≤ Number 만약 A와 B가 Number의 제곱근보다.. 2022. 3. 28.
[백준] 10757번 : 큰 수 A + B - Java https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 1. 문제 long 타입 범위 : (-263) ~ (263 - 1) 문제 내의 주어진 범위 : 1010000 ➡ long 타입 범위 초과 2. 방법 2.1. 덧셈 과정 직접 구현 [예시] [각 자리수] 10으로 나눈 나머지 값 저장 10이 넘을 경우 올림 발생 ➡ 다음 자리수에 +1 2.2. Java의 BigInteger 클래스 활용 BigInteger : 클래스 객체 ➡ 선언 및 생성 필수 Big Integer 생성 시 파라미터로 문자열 넘겨줘야 함 3. 구현 방법 Scanner + 직접 구현 .. 2022. 3. 26.
[백준] 2839번 : 설탕 배달 - Java https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 알고리즘 문제 봉지 개수 최소화 최대한 5kg 봉지로 구성해야 함 순서 5로 나누어 떨어지는 수 5로 나누어 떨어지지 않는 수 (N / 5) 값과 (N % 5) 값 파악 예외 경우 파악 결론 크게 4가지 경우로 나누자 1. N == 4 or N == 7 골드바흐의 추측 적용 주어진 조건 : 3kg, 5kg 주어진 두 소수 3, 5의 합인 8 이상의 모든 자연수는 소수의 합으로 나타낼 수 있음 ∴ 두 소수의 .. 2022. 3. 26.
[백준] 2775번 : 부녀회장이 될테야 - Java https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 주의점 가장 첫 줄 : 테스트 케이스 테스트 케이스 다음 줄부터 두 줄씩 묶어 k 와 n 이 주어짐 아파트 : 0층부터 시작, 각 층은 1호부터 시작 알고리즘 k 층 n 호 = (k-1) 층 1 호 + (k-1) 층 2 호 + ... + (k-1) 층 n 호 입력 조건 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 2022. 3. 26.
[백준] 10250번 : ACM 호텔 -Java https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 알고리즘 방 배정 우선순위 엘리베이터로부터 가까운 거리부터 배정 거리가 같은 경우 낮은 층수부터 배정 (일반 아파트 호수 매김 방법과 동일함) 1. Y (층) 구하기 int Y; if(N % H == 0) { Y = H * 100; } else { Y = (N % H) * 100; } 2. X (거리) 구하기 int X; if(N % H == 0) { X = N / H; } else .. 2022. 3. 24.
[백준] 2869번 : 달팽이는 올라가고 싶다 - Java https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 주의점 1. 시간 제한 2. 정상에 올라간 후에는 미끄러지지 않는다. 알고리즘 분석 달팽이가 하루(낮 + 밤) 동안 올라가는 높이(미터) 하루에 (A - B) 미터씩 총 V미터 BUT 달팽이가 목표 지점에 도달한 날(정상에 올라간 후)에는 미끄러지지 않는다. ➡ 총 (V - B) 미터를 올라가는 셈 결론 최소한 며칠이 걸리는지 일(日) 수 = (V - B) / (A - B) 적용 (V - B) % (A - B) == 0 남은 미터가 없다는 의미 = 정상까.. 2022. 3. 24.
[백준] 1193번 : 분수찾기 - Java https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 알고리즘 T= 분모 + 분자 대각선 칸의 개수 = T - 1 = 현 대각선의 원소의 개수 = curr_crss_cnt 초록색 T = 짝수 = (T % 2 == 0) 대각선 칸의 개수 = 홀수 좌측 하단에서 우측 상단 방향(↗) 분홍색 T = 홀수 = (T % 2 == 1) 대각선 칸의 개수 = 짝수 우측 상단에서 좌측 하단 방향(↘) 풀이 1. Scanner import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner i.. 2022. 3. 23.

티스토리툴바