공부방

탑을 내려오는 경우의 수를 찾는 문제. 블록은 인접한 아래층의 블록으로 내려오므로, 예제에서처럼 1층에서는 2개, 2층에서는 4개의 경우의 수가 발생한다. 3층의 경우를 보면 2층의 각 경우의 수마다 내려올 수 있는 선택지가 2개씩 늘어나므로 경우의 수는 8개가 된다. 1층은 2^1 2층은 2^2 3층은 2^3 ... 이 되는 것을 알 수 있다. 코드는 매우 간단하다. // 해설참조 : sehyeok.tistory.com import java.util.Scanner; public class Main { public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(..

N개 색상의 상의와 하의가 있을 때, 다른 색으로 조합하는 경우의 수를 찾는 문제. 10개가 있다고 가정하면 1번 상의는 1번 하의와 매칭할 수 없다(같은 색이므로) 즉 1번 상의와 매칭 가능한 하의의 수는 9개. 2번 상의도 마찬가지로 2번 하의를 제외한 나머지 하의와 매칭할 수 있으므로 경우의 수는 9. 3번 상의도 마찬가지로 3번 하의를 제외하므로 9개. ... 10번 상의는 10번 하의를 제외하므로 9개 이와같은 과정으로 볼 때 10개의 상의가 있다고 하면 각각이 9개의 하의와 매칭되므로 경우의 수는 10 x 9 가 되겠다. 이를 공식화하면 N개의 옷이 있다고 할 때, 조합하는 경우의 수는 N x (N - 1) 이 된다. // 해설참조 : sehyeok.tistory.com import java...

어떤 짝수 n 을 두 소수의 합으로 나타낼 수 있는데, 이 두 소수의 순서쌍의 개수를 구하는 문제이다. 앞서 사용했었던 유클리드호제법을 이용해 소수를 도출해서 계산했더니 시간 초과 에러가 나왔다. 때문에 이번에는 에라토스테네스의 체를 이용해 소수를 도출해보았다. 2020.12.08 - [Java/백준알고리즘] - 백준알고리즘 #1929 소수 구하기 java (에라토스테네스의 체) 백준알고리즘 #1929 소수 구하기 java (에라토스테네스의 체) 보기에 간단해 보이는 문제이다. sosu()메소드를 만들어서 m부터 n까지의 소수를 차례대로 구하는 코드를 작성했으나 시간 초과로 실패 이러한 시간 초과 문제를 해결하기 위해서는 에라토스테네 sehyeok.tistory.com 보다 최적화된 에라토스테네스의 체 ..

첫번째 사람부터 n번째 사람까지 차례대로 창문을 열고 닫을 때, 마지막에 열려 있는 창문의 개수를 구하는 문제. 단순히 반복문을 사용해 1부터 n까지 차례대로 닫혀있다면(0이면) 1로, 열려있으면(1이면) 0으로 바꿔준 후 1인 개수를 체크하는 식으로 풀어보았다. // 해설참조 : sehyeok.tistory.com import java.util.Scanner; public class Main { public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] ary = new int[n]; int count = 0; for (int i = 1; i

입력받은 n 보다 크거나 같은 소수 중 가장 작은 소수를 출력하는 문제. 입력받은수가 소수인지 판별하기 위해 1부터 n 혹은 n/2 까지 반복하며 약수를 확인하다보면 시간 초과 오류가 발생한다. 이는 문제에 나온 힌트처럼 루트n 까지만 나눠서 확인하면 시간 효율을 높일 수 있다. 왜 그런지 확인해보자. 예를 들어 어떤 수 N이 소수가 아닌 합성수라고 한다면, N은 어떤 약수 a와 b를 이용해 a x b 로 나타낼 수 있다. 이 때, a가 b보다 크다고 하자. 그렇다면 "a x a 는 a x b 보다 크거나 같다" 라는 것을 알 수 있다. 한 예로 100인 경우, 10^2으로 나타낼 수 있고 100의 약수는 1,2,4,5,10,20,25,50이 있는데 2 x 50, 4 x 25, 5 x 20, 10 x 1..

가로수를 같은 간격으로 심기 위한 최소수를 구하는 문제. 각 가로수 간격들의 최대공약수를 구하는 것으로 해결할 수 있어 보인다. 예제 1에서 간격들이 2 4 6이기 때문에 이들의 최대공약수는 2이고 1부터 13까지의 거리는 12이고, 이를 최대공약수로 나누면 6이 된다. 즉 1부터 13까지의 좌표 상에 총 7개 (시작점과 끝점)의 가로수가 있다고 볼 수 있다. 입력(가로수의 개수)는 4이므로 심어야하는 가로수의 최소수는 3이 되는 것이다. 조건에서 n은 3이상이고, 두 좌표 사이의 거리가 필요하기 때문에 처음 두 가로수의 좌표를 먼저 입력받는다. Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int first = sc.nextInt(); // 첫..

두 분수를 합한 수를 약분하여 기약분수로 표시하는 문제. 두 분수를 합하는 방법은 2/7 + 3/5 의 경우 분모를 통일시켜줘야 하기 때문에 2/7 에 5를 곱하고, 3/5에 7을 곱해준다. 10/35 + 21/35 즉 31/35가 되는 것. 분자는 각 분모에 곱해진 수를 곱하여 더하고, 분모는 서로 곱하면 된다. 예를 하나 더 들어 보자면. 2/5 와 1/10의 경우, 각 수에 10과 5를 곱해주면 20/50 과 5/50 이 되어 25/50이 된다. 이를 기약분수로 나타내기 위해서는 분자와 분모의 최대공약수를 이용해 나눠주면 된다. 이는 앞서 사용했었던 유클리드 호제법을 이용해 최대공약수를 이용하면 간단하다. 2023.10.10 - [Java/백준알고리즘] - [Java] 백준알고리즘 #13241 최소..

문제 설명에서 알 수 있듯이, 유클리드 호제법을 이용해 최소공배수를 구하는 문제이다. 먼저 유클리드 호제법에 대해 알아보자. 유클리드 호제법을 이용해 최대공약수를 구할 수 있다. 최대공약수를 구하면 자연스럽게 최소공배수도 구할 수 있는데, 예를 들어 35와 100의 경우 100을 35로 나눈 나머지 -> 30 35를 30으로 나눈 나머지 -> 5 30을 5로 나눈 나머지 -> 0 따라서 최대공약수는 5가 되고, 이를 이용해 최소공배수를 구하면 35 x 100 / 5 = 700 이 된다. 먼저 유클리드 호제법을 이용해 최대공약수를 구하는 식은 다음과 같다. long a = sc.nextInt(); long b = sc.nextInt(); long gcd = 0; // 최대공약수 if (a > b) { lo..

앞선 문제들을 해결할 때 사용했던 선택 정렬을 사용하면 간단하다. 2021.03.15 - [Java/백준알고리즘] - [Java] 백준알고리즘 #2798 블랙잭 [Java] 백준알고리즘 #2798 블랙잭 주어진 수들을 조합하여 3장의 카드를 골라 합이 m에 가장 근접하게 하는 문제이다. 이 문제는 선택정렬을 이용하여 풀면 간단하게 해결할 수 있다. 흔히 최소값, 최대값 또는 오름차순정렬 등을 sehyeok.tistory.com 2021.03.17 - [Java/백준알고리즘] - [Java] 백준알고리즘 #2750 수 정렬하기 [Java] 백준알고리즘 #2750 수 정렬하기 입력받은 수들을 오름차순으로 정렬하여 출력하는 문제이다. 앞서 여러 문제들을 풀면서 사용했던 선택 정렬을 이용하면 되겠다. 2021...

입력받은 5개의 수의 중간값과 평균을 구하는문제. 크기 5의 배열을 만들어서 이 배열을 크기순으로 나열하면 쉽게 해결 가능한 문제일 듯 하다. 2021.03.17 - [Java/백준알고리즘] - [Java] 백준알고리즘 #2750 수 정렬하기 [Java] 백준알고리즘 #2750 수 정렬하기 입력받은 수들을 오름차순으로 정렬하여 출력하는 문제이다. 앞서 여러 문제들을 풀면서 사용했던 선택 정렬을 이용하면 되겠다. 2021.03.15 - [Java/백준알고리즘] - [Java] 백준알고리즘 #2798 블랙잭 sehyeok.tistory.com 이전에 풀었던 선택정렬을 이용하여 배열을 크기순으로 정리. 이후 평균과 중간값을 도출하면 된다. 전체 코드는 다음과 같다. import java.util.Scanner..