0과 1의 쉼터

문제https://www.acmicpc.net/problem/2436 풀이두 수 A, B의 GCD, LCM이 주어질 때, 두 수의 합이 최소가 되는 수를 구하는 문제다.이때 두 수의 범위 2 ~ 1억에 대해 GCD, LCM을 전부 구해 비교하는 방법은 시간 초과가 발생한다.탐색 범위를 좁혀보자.$G = GCD(A, B), L = LCM(A, B)$일 때, $AB = GL$, $A = Gx$, $B = Gy$이므로 $AB = G^2xy = GL, xy = \frac{L}{G} = K$가 성립한다.K의 모든 약수 쌍 중 $GCD(A, B) = G*GCD(x, y)$를 만족해야 하므로, $GCD(x, y) = 1$인 약수만 해당된다. K = LCM // GCD x, y = 0, 0 for d ..

문제https://www.acmicpc.net/problem/1934 풀이주어진 두 자연수 A, B에 대해 LCM을 구하는 기초 문제다.두 수의 곱을 GCD로 나누면 구할 수 있다.def lcm(a, b): return int(a * b / gcd(a, b))소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/01934.py

문제https://www.acmicpc.net/problem/11772 풀이주어지는 X개의 P에 대해 ${P / 10}^{P의 1의 자리}$를 구하는 문제다. while (N-- > 0) { final int P = Integer.parseInt(br.readLine()); res += (int) Math.pow(P / 10, P % 10); }소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/11722.java

문제https://www.acmicpc.net/problem/11648 풀이주어진 수 N이 한 자리가 될 때 까지 각 자리를 곱해주는 문제다.N이 10 이상인지 확인하면서 사이클을 세주자. // Solve int happy = 0; while (N >= 10) { int temp = 1; while (N > 0) { temp *= N % 10; N /= 10; } N = temp; ++happy; }소스코드https://github.com/rogi-rogi/problem-solving/blob/main/b..

목차Primitive Array 정렬하기Object Array 정렬하기정리예제 코드Java에는 다양한 타입(Primitive / Object / Collections)의 배열이 존재할 수 있으며, 정렬하는 방식도 제각각입니다.이번 글에서는 Primitive / Object 배열을 정렬하는 방법에 대해 알아보겠습니다.1️⃣ Primitive Array 정렬하기Arrays.sort()는 원시 배열을 정렬할 수 있습니다. 기본적으로 오름차순 정렬이 되며, 내부적으로 Dual-Pivot Quicksort 알고리즘을 사용합니다SortPrimitiveArray.javaArrays.sort()를 사용해 Primitive Array를 정렬하는 방법은 다음과 같습니다.package pl.java.D250216;impor..

문제https://www.acmicpc.net/problem/3055 풀이S에 위치한 고슴도치가 비버의 굴 D로 이동하는데 필요한 최소 시간을 구하는 문제다.동시에, 물 또한 인접한 영역으로 퍼져나간다.물이 찰 예정인 영역은 고슴도치가 갈 수 없다. → 고슴도치보다 물 먼저 퍼져야 한다.물은 비버의 굴로 퍼질 수 없다.우선, 상수들을 정의해주자. final static char EMPTY = '.', WATER = '*', START = 'S', END = 'D'; static int[][] D = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; static int R, C; static char[][] board; ..

문제https://www.acmicpc.net/problem/16400 풀이N 이하의 소수들을 사용하여 N을 표현할 수 있는 방법의 수를 계산하는 문제다.우선 N이하의 소수들을 구해주자. private static boolean isPrime(int num) { final int sqrtN = (int) Math.sqrt(num) + 1; for (int i = 2; i List primeList = new ArrayList(); for (int i = 2; i dp[i] : 소수들의 합으로 숫자 i를 만드는 경우의 수dp[i]의 i는 소수의 합이기 때문에 dp[i]는 dp[i - prime]에 prime을 더하는 경우의 수를 누적하면 된다.즉 i..

목차왜 원시 배열은 내림차순 정렬을 지원하지 않을까?원시 배열을 내림차순 정렬하는 방법정리예제 코드자바에서는 Arrays.sort() 를 사용해 원시(Primitive) 배열을 쉽게 정렬할 수 있습니다. 하지만 원시 타입 배열에 대해 내림차순 정렬은 지원되지 않습니다.이 글에서는 원시 배열에 내림차순 정렬이 지원되지 않는 이유와, 이를 해결할 수 있는 대안에 대해 알아보겠습니다.1️⃣ 왜 원시 배열은 내림차순 정렬을 지원하지 않을까?원시 배열은 기본적으로 객체가 아니기 때문에 Comparator를 사용할 수 없습니다.Arrays.sort()는 원시 타입 배열에 대해 Comparator를 지원하지 않으므로, 정렬 순서를 커스터마이즈할 수 없습니다. 반면, 객체 타입 배열(Integer[], Double[]..

문제https://www.acmicpc.net/problem/11520 풀이단순한 구현 문제다.입력받는 P, D에 대해 다음을 만족하는 Q, R 번째의 수를 출력하면 된다.Q : π에 대해 P이상인 Q번째 자리가 D인 최소 자리 QR : π에 대해 Q초과인 R번째 자리가 5인 최소 자리 R즉 정리하면 입력받은 D와 5를 출력하면 된다. while (N-- > 0) { // Solve sb.append(Integer.parseInt(br.readLine().split(" ")[1])).append(" ").append(5).append("\\n"); }소스코드https://github.com/rogi-rogi/problem-solving/bl..

문제https://www.acmicpc.net/problem/11466 풀이주어진 직사각형에서 최대 크기의 정사각형 3개를 만들 때 정사각형 한 변의 최대 길이를 구하는 문제다.우선, W와 H에 대해 W ≤ H가 되도록 값을 교환하자. // Solve if (W > H) { double temp = W; W = H; H = temp; }이제 직사각형에 정사각형을 배치할 수 있는 방법은 다음과 같이 두 가지가 존재하다.한 줄에 3개의 정사각형 배치두 줄로 배치결국 W와 H에 대해 더 작은 값으로 정사각형을 만들어야 한다.두 경우에 대해 최솟값을 구해주고, 이 중 더 큰 정사각형의 한 변을 구해주자. ..