본문 바로가기

코딩테스트 준비628

[백준] 1932번 - 정수 삼각형 [Java] https://www.acmicpc.net/problem/1932 1.  아이디어 Bottom-Up 다이나믹 프로그래밍을 활용해서 해결했다. 삼각형의 크기가 최대 500이어서 DFS 알고리즘으로는 해결할 수 없다.2. 문제풀이 정수 삼각형에서 특정 위치에 대한 최대 경로를 저장하는 dp 배열을 사용했다. 각 위치는 위쪽 두 위치에 대해 최대 경로에 현재 숫자를 더하는 방식으로 점화식을 구성할 수 있고 dp 배열을 모두 채운 후 맨 아래층을 순회하며 최댓값을 찾는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 1. 22.
[백준] 2579번 - 계단 오르기 [Java] https://www.acmicpc.net/problem/2579 1.  아이디어 Bottom-Up 다이나믹 프로그래밍을 활용해서 해결했다. 3개의 계단을 연속해서 오를 수 없는 조건은 2칸 이전 계단에서 얻은 최댓값에서 현재 칸에서 얻는 점수와 3칸 이전 계단에서 얻은 최댓값에 1칸 이전에서 얻은 점수와 현재 칸에서 얻은 점수의 합을 비교하면 된다.2. 문제풀이 구현의 편의를 위해 배열로 다룰 때 앞쪽에 패딩을 넉넉하게 주는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR.. 2025. 1. 22.
[백준] 11660번 - 구간 합 구하기 5 [Java] https://www.acmicpc.net/problem/11660 1.  아이디어 누적합 배열을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 주어진 영역에 대해 특정 영역의 합을 반복해서 구하는 문제로 2차원 누적합 배열을 생성한 후 prefixSum[x2][y2] - prefixSum[x2][y1] - prefixSum[x1][y2] + prefixSum[x1][y1] 점화식으로 간단하게 특정 영역의 합을 구할 수 있는 점을 활용해 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReade.. 2025. 1. 21.
[백준] 11659번 - 구간 합 구하기 4 [Java] https://www.acmicpc.net/problem/11659 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)); BufferedWriter bw = .. 2025. 1. 21.
[백준] 11727번 - 2×n 타일링 2 [Java] https://www.acmicpc.net/problem/11727 1.  아이디어 이전 2×n 타일링 문제에서 2 * 2 타일이 추가된 문제로 동일하게 Bottom-Up 다이나믹 프로그래밍으로 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 11726번 - 2×n 타일링 [Java])2. 문제풀이 이전 문제 점화식에서 N-2 일 때 2 * 2 타일을 붙이는 옵션만 추가된 문제로 dp[i] = dp[i-1] + 2 * dp[i-2]로 간단하게 점화식을 구할 수 있다.3. 코드 import java.io.*;public class Main { private static final int MOD = 10_007; public static void main(String[] args).. 2025. 1. 21.
[백준] 11726번 - 2×n 타일링 [Java] https://www.acmicpc.net/problem/11726 1.  아이디어 Bottom-Up 다이나믹 프로그래밍으로 간단하게 해결할 수 있다.2. 문제풀이 1차원 dp 배열을 선언해서 특정 길이일 때 직사각형을 채우는 방법의 수를 저장했다. 길이가 N인 직사각형을 채우는 방법의 수는 길이 N-1일 때 직사각형을 채우는 모든 케이스에 1 x 2 타일 하나를 붙이는 경우와 길이 N-2일 때 직사각형을 채우는 모든 케이스에 2 x 1 타일을 위아래 채우는 경우의 합으로 간단하게 점화식을 구할 수 있다.3. 코드 import java.io.*;public class Main { private static final int MOD = 10_007; public static void main(S.. 2025. 1. 21.
[벌집] 27436번 - 벌집 2 [Java] https://www.acmicpc.net/problem/27436 1.  아이디어 이전 벌집 문제에서 N의 크기가 매우 커진 문제로 이전처럼 O(N) 시간복잡도의 풀이로는 해결할 수 없다. 이를 단축하기 위해 O(log N)으로 풀 수 있는 이분 탐색으로 방의 개수를 찾는 방식을 적용했다.([코딩테스트 준비/백준] - [백준] 2292번 - 벌집 [Java])2. 문제풀이 이분 탐색은 N 이상인 최솟값을 찾아야하므로 Lower Bound 이분 탐색을 적용했다. 이전 문제와 동일한 점화식 Sn = 3 * n * (n-1) + 1을 가져와서 n을 찾는 이분 탐색으로 적용했다. 대략 2 * 10^9 이면 주어진 N까지 커버할 수 있는 범위라서 아래 코드처럼 적용했는데 실제 풀이에서는 적당한 high 값을 찾.. 2025. 1. 21.
[백준] 9663번 - N-Queen [Java] https://www.acmicpc.net/problem/9663 1.  아이디어 순열에 기반한 재귀 메서드와 방문 체크를 통해 해결할 수 있다.순열의 depth를 열, 값을 행에 매핑해서 행과 열에 대한 중복을 미리 제거하고 대각선은 행과 열의 합과 차를 통해 방문 체크를 적용할 수 있다.2. 문제풀이 0부터 N-1까지의 수 중에서 N개를 중복없이 뽑는 순열을 적용하면 바로 행과 열에 대한 중복 없는 퀸의 배치들을 얻을 수 있다. 이때 같은 대각선에 있는지 파악하는 방법은 우상좌하 대각선에서 같은 대각선에 있으면 행과 열의 합이 동일하고, 좌상우하 대각선에서 같은 대각선에 있으면 행과 열의 차가 동일하다는 점으로 백트래킹을 적용하는 방식으로 구현했다.3. 코드 import java.io.*;public.. 2025. 1. 21.
[백준] 11057번 - 오르막 수 [Java] https://www.acmicpc.net/problem/11057 1.  아이디어 행에는 자리수, 열에는 각 자리수에 들어가는 숫자를 저장하는 2차원 dp 배열을 활용한 다이나믹 프로그래밍으로 해결할 수 있었다.2. 문제풀이 오르막 수가 0으로 시작할 수 있어서 풀이가 더 단순했다. 오르막 수를 만들 때 자리수를 뒤로 추가한다고 하면 이전 오르막 수의 1의 자리수보다 같거나 큰 수들이 올 수 있다. N = 1 일 때 0부터 9까지 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 개가 각각 들어가게 되고 N = 2 일 때는 10, 9, 8, 7, 6, 5, 4, 3, 2, 1개가 각각 들어가게 된다. 이를 통해 각 열에 대해 역순으로 순회하며 dp[i][j] =  dp[i-1][j] + dp[i][j.. 2025. 1. 21.
[백준] 11048번 - 이동하기 [Java] https://www.acmicpc.net/problem/11048 1.  아이디어 Bottom-Up 다이나믹 프로그래밍으로 간단하게 해결할 수 있다.2. 문제풀이 미로와 같은 크기의 2차원 dp 배열을 선언했다. dp 배열에는 미로와 같은 위치에서 가져올 수 있는 사탕 개수의 최댓값을 저장했다. 점화식은 dp 배열의 현재 위치에서 얻을 수 있는 사탕의 최대 개수는 현재 위치에 오기 이전 위치에서 얻을 수 있는 사탕의 최대 개수에서 현재 위치에서 얻을 수 있는 사탕의 개수를 더하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException .. 2025. 1. 21.
[백준] 1890번 - 점프 [Java] https://www.acmicpc.net/problem/1890 1.  아이디어 Top-Down 다이나믹 프로그래밍으로 해결했다.2. 문제풀이 시작 위치를 기준으로 재귀 메서드를 구성하고 이를 메모이제이션을 활용해서 구현했다. 재귀는 위치 정보를 받아서 현재 위치가 도착위치면 1을 반환하고 현재 위치가 점프가 불가능한 0이면 0을 반환하게 했다. 이후 cnt 변수를 통해 현재 위치에서 도착 칸에 갈 수 있는 경우의 수를 각 점프에서 구해서 반환하게 구성했고 이를 dp 배열에 저장했다. 재귀 과정에서 dp 배열이 0이 아닌 해당 칸에서 도착 칸에 갈 수 있는 경우가 저장된 경우 재귀 없이 바로 해당 값을 반환하게 메모이제이션을 적용했다. 일반적인 완전 탐색으로는 시간 초과가 발생하게 돼서 메모이제이션이 .. 2025. 1. 21.
[백준] 1699번 - 제곱수의 합 [Java] https://www.acmicpc.net/problem/1699 1.  아이디어 Bottom-Up 다이나믹 프로그래밍으로 해결했다.2. 문제풀이 주어진 숫자를 최소 개수의 제곱수의 합으로 만들어내는 문제로 dp 배열을 선언한 후 제곱수들은 1로 나머지 수는 무한대로 초기화했다. 이후 dp 배열을 순회하며 각 숫자에 대해 해당 숫자보다 작은 제곱수를 뺀 숫자와 비교해서 최솟값을 저장하는 방식으로 점화식을 구성해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buff.. 2025. 1. 21.

티스토리툴바