수학103 [백준] 1193번 - 분수찾기 [Java] https://www.acmicpc.net/problem/1193 1. 아이디어 분수를 찾는 과정에서 배열을 지그재그로 탐색한다. 이때 같은 대각선에 위치하는 수들은 분자와 분모의 합이 동일하다는 점과 대각선에 있는 수의 크기가 1, 2, 3 이렇게 선형적으로 증가함을 활용하면 해결할 수 있다.2. 문제풀이 X가 존재하기 이전 대각선까지의 모든 수의 개수를 구해서 sum 변수에 저장했다. 이후 N이 짝수번째 대각선이냐 홀수번째 대각선이냐에 따라 시작 위치만 바꿔서 위치를 찾아주는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { Buf.. 2025. 2. 6. [백준] 17427번 - 약수의 합 2 [Java] https://www.acmicpc.net/problem/17427 1. 아이디어 문제의 설명대로 1부터 N까지 각 자연수의 약수의 합을 구하고 이를 다시 더하는 방식으로는 시간안에 해결할 수 없다. 반대로 1부터 N까지의 수가 g(N)에 몇 번 등장할지를 찾으면 간단하게 해결할 수 있는데 1은 1부터 N까지 1의 배수의 수만큼 등장하고 2는 2의 배수의 수만큼 등장하고 3은 3의 배수의 수만큼 등장한다. 이를 활용하면 간단하게 해결할 수 있다.2. 문제풀이 배수는 나눗셈 연산으로 구할 수 있고 등장한 수의 합을 구하기 위해 해당 수를 곱하는 과정을 반복하면 간단하게 해결할 수 있다. g(N)을 구하는 과정에서 int형 오버플로우가 발생할 수 있음에 주의해야한다.3. 코드 import java.io.*.. 2025. 2. 6. [백준] 5619번 - 세 번째 [Java] https://www.acmicpc.net/problem/5619 1. 아이디어 두 수를 붙여서 만든 수들 중 세 번째로 작은 수를 구하는 문제로 수어진 수열을 크기 순으로 정렬했을 때 5번째 이상으로 큰 수를 사용해서 세 번째로 작은 수를 만들 수 없음을 이용했다.2. 문제풀이 주어진 수열의 길이가 3일 경우 3가지 수의 조합들 중 정답이 있고, 주어진 수열의 길이가 4 이상일 경우 주어진 수열을 정렬했을 때 가장 작은 4가지 수들의 조합 중 정답이 있다. 해당 조합들을 우선순위 큐에 넣은 후 세 번째 수를 뽑아내는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(Strin.. 2025. 2. 4. [백준] 1094번 - 막대기 [Java] https://www.acmicpc.net/problem/1094 1. 아이디어 이 문제는 1부터 64 사이의 2의 제곱수로 X를 만드는 문제와 동일한 문제가 된다. 64부터 1까지 반복문을 통해 제곱수의 개수를 세는 방식으로 간단하게 해결할 수 있고 비트마스킹을 활용해 X를 2진수로 나타냈을 때 1의 개수를 세는 방식으로도 해결할 수 있다.2. 문제풀이 기본 구현은 for문의 인덱스를 2로 나눠가며 1의 개수를 세도록 구현했고, 비트마스킹의 경우 bitCount 메서드로 1인 비트의 개수를 간단하게 셀 수 있다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 2. 4. [백준] 16504번 - 종이접기 [Java] https://www.acmicpc.net/problem/16504 1. 아이디어 종이접기 과정에서 겹치는 두 수를 더하는 과정을 반복하게 되는데 이때 1 x 1 크기까지 접으면 종이의 모든 수를 더한 수가 남게 된다.2. 문제풀이 주어진 모든 수를 더해서 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; .. 2025. 2. 4. [백준] 11051번 - 이항 계수 2 [Java] https://www.acmicpc.net/problem/11051 1. 아이디어 이전 이항 계수 문제에서 수의 범위가 커진 문제로 단순한 재귀 대신 다이나믹 프로그래밍을 활용해서 해결할 수 있다.2. 문제풀이 Top-Down, Bottom-Up 두 가지 방식으로 구현했는데 Top-Down 방식은 기존의 재귀 함수에서 행을 N, 열을 K로 하는 2차원 dp 테이블을 설정해서 dp 테이블에 값이 있으면 바로 반환하고 기존의 반환값도 dp 테이블에 저장하는 방식으로 구현했다. Bottom-Up 방식은 똑같은 dp 테이블에서 조합 점화식을 적용해 반복문으로 구하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_TopDown_DP .. 2025. 2. 3. [백준] 11050번 - 이항 계수 1 [Java] https://www.acmicpc.net/problem/11050 1. 아이디어 작은 크기의 이항 계수를 구하는 문제로 조합 공식 nCk = n-1Ck-1 + n-1Ck 를 재귀적으로 구현해서 해결했다.2. 문제풀이 nC1 = n, nC0 = 1, nCn = 1 이 재귀 함수의 종료 조건이 되게 설정하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); St.. 2025. 2. 3. [백준] 17252번 - 삼삼한 수 [Java] https://www.acmicpc.net/problem/17252 1. 아이디어 N부터 N보다 작은 3의 제곱 수 중 가장 큰 수를 빼는 과정을 반복하면 간단하게 해결할 수 있다.2. 문제풀이 2,147,483,647보다 작은 3의 제곱수 중 가장 큰 수가 1162261467인 점을 활용해 for문에서 인덱스를 3으로 나눠가며 계산하는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int.. 2025. 2. 2. [백준] 2527번 - 직사각형 [Java] https://www.acmicpc.net/problem/2527 1. 아이디어 조건 분기로 해결할 수 있는 문제로 d -> c -> b -> a 순으로 찾아나갔다.2. 문제풀이 d는 각 변의 위치 관계, c는 각 꼭짓점의 위치 관계, b도 각 변의 위치 관계로 간단히 찾을 수 있어서 해당 방식으로 if else if else 조건 분기로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System... 2025. 2. 2. [백준] 2749번 - 피보나치 수 3 [Java] https://www.acmicpc.net/problem/2749 1. 아이디어 피보나치 수의 N이 매우 커진 문제로 거듭제곱의 분할 정복과 점화식의 행렬 변환으로 해결할 수 있다.2. 문제풀이 피보나치 수열은 a(n) = a(n-1) + a(n-2)의 점화식을 갖는데 이를 다음과 같이 행렬의 거듭제곱으로 표현할 수 있다. $\begin{pmatrix}a_{n}\\ a_{n-1}\end{pmatrix} =\begin{pmatrix}a_{n-1}+a_{n-2}\\ a_{n-1}\end{pmatrix} =\begin{pmatrix}1&1\\ 1&0\end{pmatrix} \begin{pmatrix}a_{n-1}\\ a_{n-2}\end{pmatrix}$ $\begin{pmatrix}a_{n}\\ a_{n-.. 2025. 2. 2. [백준] 11444번 - 피보나치 수 6 [Java] https://www.acmicpc.net/problem/11444 1. 아이디어 이전 피보나치 수 문제에서 나누는 수만 달라진 문제로 동일한 로직으로 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 2749번 - 피보나치 수 3 [Java])2. 문제풀이 아이디어 그대로 구현했다.3. 코드 import java.io.*;public class Main { private static final long[][] baseMatrix = { {1, 1}, {1, 0} }; private static final int MOD = 1_000_000_007; public static void main(String[] args) throws IOE.. 2025. 2. 2. [백준] 25426번 - 일차함수들 [Java] https://www.acmicpc.net/problem/25426 1. 아이디어 ax + b꼴의 일차함수에서 x에 서로 다른 정수를 대입할 때 최댓값으로 b는 상관없이 a와 x의 곱이 최대가 되야하고 이는 a가 클수록 x에 대입할 정수도 큰 수를 넣으면 된다.2. 문제풀이 계수 a에 대해 정렬한 후 순서대로 x에 1부터 N까지 넣으면 되므로 2차원 배열로 두 정수를 저장 후 a에 대해 정렬하고 값을 대입하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new .. 2025. 2. 1. 이전 1 2 3 4 5 ··· 9 다음
