본문 바로가기

Algorithm/Baekjoon82

[백준] 3053번 : 택시 기하학 - Java https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net 택시 기하학 = 맨해튼 거리, Manhatten distance 빨간색 길이 = 파란색 길이 = 노란색 길이 ➡ 2차원 평면에서 가로를 x, 세로를 y라 할 때, 택시 기하학에서의 거리 = 두 점의 x 좌표 차 + 두 점의 y 좌표 차 유클리드 기하학 택시 기하학 * 그림 상의 초록색 선 * 우리가 평소에 아는 '거리' 개념 D(T₁, T₂)² = (𝑥₁ - 𝑥₂)² + (y₁ - y₂)² 원의 넓이 = 𝜋𝑟² = 3 .. 2022. 4. 4.
[백준] 4153번 : 직각삼각형 - Java https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 알고리즘 피타고라스의 정리 활용 a2 = b2 + c2 풀이 1. Scanner import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while(true) { int x = in.nextInt(); int y = in.nextInt(); int z .. 2022. 4. 1.
[백준] 3009번 : 네 번째 점 - Java .https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 직사각형 만들기 위해 총 4개의 좌표(x, y) 필요 4개의 좌표 기준, 각 좌표의 x와 y값은 쌍을 이룸 쌍을 이루지 않는 (x, y) 좌표 구하기 예시 4개의 좌표 주어짐 (2, 1), (4, 1), (2, 3), (4, 3) * x 좌표 종류 : 2, 4 (각 2개씩) * y 좌표 종류 : 1, 3 (각 2개씩) 3개의 좌표가 주어질 때 나머지 하나의 좌표 구하는 방법 x = x가 쌍을 이루지 않는 좌표 y = y가 쌍을 이루지 않는 좌표 ➡ 쌍을 이루지 않는 .. 2022. 3. 31.
[백준] 1085번 : 직사각형에서 탈출 - Java https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 알고리즘 직사각형의 경계선까지 가는 거리의 최솟값 (x,y) 위치 기준으로 상, 하, 좌, 우 중 최소값 구하기 풀이 1. Scanner import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int x = in... 2022. 3. 30.
[백준] 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.

티스토리툴바