알고리즘/백준 문제 및 정답
문제 번호 25501번 : 재귀의 귀재 - JAVA [자바]
문제 번호 25501번 : 재귀의 귀재 - JAVA [자바]
2022.12.15https://www.acmicpc.net/problem/25501 25501번: 재귀의 귀재 각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다. www.acmicpc.net 문제 설명 문자열에 앞뒤가 같은지 재귀를 사용하여 확인하는 문제입니다. 문제 풀이 사실 문제속에 정답이 다 있습니다. 문제를 보고 조금 당황했어요. 반복문과 출력만 해주면 됩니다. import java.util.Scanner; public class Main { static int count = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n ..
문제 번호 10870번 : 피보나치 수 5 - JAVA [자바]
문제 번호 10870번 : 피보나치 수 5 - JAVA [자바]
2022.12.14https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 설명 피보나치 수열은 유명한 수열문제중에 하나입니다. 재귀를 이용해 풀어보도록 하겠습니다. 문제 풀이 재귀 문제를 만나면 어떻게 재귀를 만들어야 하는지 막막 할 수 있습니다. 그럴때는 먼저 반복문으로 해당 문제를 풀어보는 것이 중요합니다. 그러면 어떻게 재귀를 사용해야하는지 감이 오기 시작합니다. 반복문으로 다음과 같이 할 수 있습니다. public s..
문제 번호 10872번 : 팩토리얼 - JAVA [자바]
문제 번호 10872번 : 팩토리얼 - JAVA [자바]
2022.12.14https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 하나의 수가 주어지면 그 수부터 1까지 모든 수를 곱한 수를 구하는 문제입니다. 재귀를 이용하여 풀어보겠습니다. 문제 풀이 사실 이 문제에서 재귀와 반복문이 다를 것이 없습니다. 어떻게 재귀를 반복문처럼 쓰는지 밑에 코드로 보여드리겠습니다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //팩토리얼 변수 int n =..
문제 번호 2738번 : 행렬 덧셈 - JAVA [자바]
문제 번호 2738번 : 행렬 덧셈 - JAVA [자바]
2022.12.12https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 문제 설명 크기가 10*10=100인 색종이의 크기를 구하는 문제입니다, 단 겹치는 부분까지 계산해야 합니다. 문제 풀이 해당 문제를 생각보다 많이 고민했습니다. 겹치는 부분을 찾아서 그부분을 빼주면 될거라고 생각하고 코드를 짜봤는데 너무 복잡해졌습니다. 그래서 좌표가 100 이하라는 사실에 집중해서 해당 좌표를 2차원 배열 0으로 선언하고 출발점 좌표부터 10*10만큼 해당 좌표를 모두 1로 만들어..
문제 번호 9020번 : 골드바흐의 추측 - JAVA [자바]
문제 번호 9020번 : 골드바흐의 추측 - JAVA [자바]
2022.09.15https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 설명 골드바흐의 추측에 관련된 문제로 입력받은(무조건 짝수) 수를 만드는 합인 두 수를 구하는 문제입니다. 이때 두 수는 소수이여야 합니다. 문제 풀이 소수를 구하는 알고리즘은 에라토스테네스의 체 알고리즘을 사용했습니다. 이 알고리즘의 자세한 설명은 다음 게시물에 있습니다. https://kkungchan.tistory.com/266 8단계 문제 번호 1929번 : 소수 ..
문제 번호 4948번 : 베르트랑 공준 - JAVA [자바]
문제 번호 4948번 : 베르트랑 공준 - JAVA [자바]
2022.09.13https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 설명 여러 숫자를 입력받은 후에 그 수부터 2n까지의 소수의 개수를 구하는 문제입니다. 문제 풀이 알고리즘은 에라토스테네스의 체 알고리즘을 사용했습니다. 이 알고리즘의 자세한 설명은 다음 게시물에 있습니다. https://kkungchan.tistory.com/266 8단계 문제 번호 1929번 : 소수 구하기 - JAVA [자바] https://www.acmicpc.net/probl..
문제 번호 1929번 : 소수 구하기(에라토스테네스의 체) - JAVA [자바]
문제 번호 1929번 : 소수 구하기(에라토스테네스의 체) - JAVA [자바]
2022.09.12https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 설명 주어진 수의 사이에 있는 소수를 구하는 문제입니다. 문제 풀이 정말 오래 걸리고 골치 아팠던 문제입니다. 소수 구하는 공식은 사실 어렵지 않은데 계속 속도 이슈가 걸리는 문제가 있었습니다. 여기서 에라토스테네스의 체 알고리즘을 사용해서 풀면 속도 이슈가 해결되지만 이 알고리즘을 이해하기까지 오랜 시간이 걸렸습니다. 최대한 저의 수준에서 이해할 수 있도록 코드를 해석하고 설명해 놓았으니 도움이 되었으면 좋겠습니다. im..
문제 번호 11653번 : 소인수분해 - JAVA [자바]
문제 번호 11653번 : 소인수분해 - JAVA [자바]
2022.05.05https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 설명 주어진 수를 소수인수분해 한 후에 소인수 분해 한 수를 출력하는 문제입니다. 문제 풀이 소인수분해란 해당 수를 가장 작은 수로 분해하는 것을 말합니다. 예를 들어 18이란 숫자를 소인수분해 한다고 하면 가장 작은 수인 2로 나누면 9가 되고 9는 2로는 나눠지지 않으니 다음 큰 수인 3으로 나눠 2*3*3 = 9 라는 식을 만드는 것이 소인수분해 입니다. 여기서 저 곱들이 모두 소수여서 소인수분해라고 하는 것이죠. 그럼 이것을 어떻게 로직으로 만들지 생각해 봅시다. 소인수분해는 가장 작은 순서대로 나눠 곱..
문제 번호 1978번 : 소수 찾기 - JAVA [자바]
문제 번호 1978번 : 소수 찾기 - JAVA [자바]
2022.04.23https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 문제 설명 주어진 수를 소수인지 아닌지 확인 한 후에 전체 총합과 가장 작은 수를 구하는 문제입니다. 문제 풀이 https://kkungchan.tistory.com/258 8단계 문제 번호 1978번 : 소수 찾기 - JAVA [자바] https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어..
문제 번호 1978번 : 소수 찾기 - JAVA [자바]
문제 번호 1978번 : 소수 찾기 - JAVA [자바]
2022.04.23https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 설명 주어진 수가 소수인지 아닌지 확인하는 문제입니다. 문제 풀이 주어진 수가 소수인지 아닌지 맞추면 된는 아주 간단한 문제입니다. 소수는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수. 입니다. 주어진 수를 1과 자기 자신을 제외한 주어진 수보다 작은 모든 수로 나눠보고 나머지가 0이 있으면 소수가 아니게 됩니다. 위에는 사실 소수를 구하는 공식입니다. 더 깊이 들어가면 사실은 자연수 n이 소수인지 아닌지를 판정하려면, 인 범위에 있는 모든 소수..
문제 번호 10757번 : 큰 수 A+B - JAVA [자바]
문제 번호 10757번 : 큰 수 A+B - JAVA [자바]
2022.04.13https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 10의 10000제곱 승까지 범위에 수를 더하는 프로그램을 만드는 문제입니다. 문제 풀이 자바에서는 큰 수를 구하는 java.math 라이브러리가 있음으로 사용하면 아주 편합니다. integer형의 범위 밖에 있는 수를 계산할 때 사용하면 됩니다. 자세한 내용은 아래 게시물로 가시면 확인할 수 있습니다. https://kkungchan.tistory.com/256 Java 기초 함수 - BigInteger(큰 정수) 기본 환경 JDK : 1.8.0_261 버전 JRE : 1.8.0_261 버전 ..
문제 번호 2839번 : 설탕 배달 - JAVA [자바]
문제 번호 2839번 : 설탕 배달 - JAVA [자바]
2022.03.04https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 설명 Nkg의 설탕을 3kg 봉지와 5kg의 봉지에 나누어 담되 봉지수가 최소가 되게 해 달라는 문제입니다. 간단하게 (3*x) + (5*y) = N인데 x+y의 최솟값을 구하라는 문제입니다. 정말 많은 풀이법이 있지만 가장 직관적인 방법과 가장 간결한 방법의 코드 두 가지를 소개하겠습니다. 문제 풀이 1. 직관적인 풀이 저는 직관적인 풀이를 더 좋아합니다. 알아보기도 쉽고 유지 보수에 도움이 되기 때..