본문 바로가기

코딩테스트 준비461

[백준] 1182번 - 부분수열의 합 [Java] https://www.acmicpc.net/problem/1182 1.  아이디어 부분집합을 통해 수열을 뽑아서 더하는 방식으로 해결할 수 있다.2. 문제풀이 모든 부분집합을 구하는 powerSet 메서드를 작성해서 집합이 생성되면 그 합을 S와 비교하는 방식으로 구현했다. 부분수열은 연속이 아니어도 됨에 주의해야하고 부분수열의 크기가 양수여야해서 S가 0일 경우 아무것도 선택하지 않는 공집합이 카운팅될 수 있음에 주의해야한다.3. 코드 import java.io.*;import java.util.*;public class Main { private static int N; private static int S; private static int[] arr; private stati.. 2025. 1. 23.
[백준] 1788번 - 피보나치 수의 확장 [Java] https://www.acmicpc.net/problem/1788 1.  아이디어 N이 0일 때 양수일 때, 음수일 때를 나눠서 해결했다.2. 문제풀이 N이 0일 경우 0 두개를 출력하고 종료했고 N이 양수일 경우 일반적인 다이나믹 프로그래밍을 활용한 피보나치 구현으로, N이 음수일 경우 이항을 통해 점화식을 구해서 동일하게 다이나믹 프로그래밍으로 해결했다. N이 음수일 경우 필요에 따라 절댓값으로 양수처리를 해줘야 한다.3. 코드 import java.io.*;public class Main { private static final int MOD = 1_000_000_000; public static void main(String[] args) throws IOException { .. 2025. 1. 23.
[백준] 2193번 - 이친수 [Java] https://www.acmicpc.net/problem/2193 1.  아이디어 N자리 이친수는 N-1자리 이친수 뒤에 0을 하나 더 붙이거나 N-1자리 이친수 중 0으로 끝나는 이친수 뒤에 1을 붙여서 만들 수 있다.2. 문제풀이 N이 최대 90까지라서 int형 오버플로우가 발생하는 점만 주의하면 된다. 추가로 규칙성을 통해 피보나치 수열을 이루는 점을 알 수 있어서 이를 활용한 1차원 dp 배열로도 해결할 수 있었다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu.. 2025. 1. 23.
[백준] 4179번 - 불! [Java] https://www.acmicpc.net/problem/4179 1.  아이디어 이전 불 문제와 거의 동일한 문제로 지훈이와 불에 대해 각각 Queue를 사용한 BFS 알고리즘을 활용하면 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 5427번 - 불 [Java])2. 문제풀이 지훈이는 방문 체크 배열로, 불은 원본 맵을 변경하는 방식으로 구현했다. 불이 이제 붙으려는 칸으로도 이동할 수 없다는 점에서 불을 먼저 이동시키고 지훈이의 이동을 체크해야하며 최단 거리 BFS로 구현하는 과정에서 각각 Queue의 크기만큼 반복하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final in.. 2025. 1. 23.
[백준] 5427번 - 불 [Java] https://www.acmicpc.net/problem/5427 1.  아이디어 상근이와 불에 대해 각각 Queue를 사용한 BFS 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 상근이는 방문 체크 배열로, 불은 원본 맵을 변경하는 방식으로 구현했다. 불이 이제 붙으려는 칸으로도 이동할 수 없다는 점에서 불을 먼저 이동시키고 상근이의 이동을 체크해야하며 최단 거리 BFS로 구현하는 과정에서 각각 Queue의 크기만큼 반복하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final int[] dr = {-1, 0, 1, 0}; private static final int[] dc = .. 2025. 1. 23.
[백준] 7569번 - 토마토 [Java] https://www.acmicpc.net/problem/7569 1.  아이디어 이전 토마토 문제의 입체 버전으로 역시 BFS 알고리즘을 활용하면 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 7576번 - 토마토 [Java])2. 문제풀이 2차원이었던 상자를 3차원으로 바꿔주고 상하를 포함한 6방 탐색으로 변경하면 간단하게 구현할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final int[] dr = {-1, 0, 1, 0, 0, 0}; private static final int[] dc = {0, 1, 0, -1, 0, 0}; private static fin.. 2025. 1. 23.
[백준] 7576번 - 토마토 [Java] https://www.acmicpc.net/problem/7576 1.  아이디어 BFS 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 BFS의 Queue에는 익은 토마토들을 담고 인접한 익지 않은 토마토가 익게 되므로 Queue에 넣으면 된다. 최단 거리 BFS를 기반으로 구현했으며 최초에 익지 않은 토마토의 개수를 세고 익을 때마다 개수를 빼줬을 때 0이 돼서 모든 토마토가 익었는지 여부도 판단할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final int[] dr = {-1, 0, 1, 0}; private static final int[] dc = {0, 1, 0, -1.. 2025. 1. 23.
[백준] 1149번 - RGB거리 [Java] https://www.acmicpc.net/problem/1149 1.  아이디어 다이나믹 프로그래밍을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 윗집과 아랫집과는 다른 색으로 칠해야하는 문제로 사실 윗집만 고려하면 된다. dp 배열에는 현재 집을 칠하는 경우 칠하는 비용의 최솟값을 저장한다고 할 때 현재 집과 색이 다른 두 윗집 중 칠하는 비용의 누적값이 최소인 집을 고르고 현재 집을 고르면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReade.. 2025. 1. 23.
[백준] 2580번 - 스도쿠 [Java] https://www.acmicpc.net/problem/2580 1.  아이디어 재귀와 백트래킹을 통해 해결할 수 있는 문제로 DFS 알고리즘과 중복 순열 두 가지 방법으로 해결했다.2. 문제풀이 DFS는 0행 0열부터 8행 8열까지 행 우선 순회하며 0이 아니면 다음 재귀로 넘어가고 0이면 1부터 9까지 넣어보고 다음 재귀로 넘어가도록 구현했다. 재귀 과정에서 1부터 9까지 전부 넣을 수 없으면 이전 재귀에서 잘못된 숫자가 들어갔던 것이므로 이전 재귀로 돌아가면 이전 재귀의 숫자를 안넣었던 것으로 처리하는 방식으로 구현했다. 행과 열, 정사각형에 대한 방문 체크로 숫자를 넣을 수 있는지 이때 방문 체크 배열은 3차원으로 만들어서 각 위치에 들어갈 수 없는 숫자를 등장 횟수로 구분했다. 단순히 bool.. 2025. 1. 23.
[백준] 1389번 - 케빈 베이컨의 6단계 법칙 [Java] https://www.acmicpc.net/problem/1389 1.  아이디어 케빈 베이컨 수는 그래프에서 특정 노드와 다른 모든 노드와의 거리의 합과 같다. 각 사람에 대해 BFS 알고리즘으로 거리를 구해서 더하는 방식과 플로이드 워셜 알고리즘으로 거리 배열을 구해서 더하는 방법 두가지로 해결할 수 있었다.2. 문제풀이 - BFS친구관계가 중복으로 들어올 수 있어서 인접 리스트에 Set을 적용해서 중복을 제거하는 방식으로 구현했다. - 플로이드 워셜 알고리즘각 친구들과의 거리 정보를 담은 거리 배열을 생성한 후 각 행 또는 열의 합으로 케빈 베이컨 수를 간단하게 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { .. 2025. 1. 23.
[백준] 10026번 - 적록색약 [Java] https://www.acmicpc.net/problem/10026 1.  아이디어 적록색약인 사람은 R과 G를 동일하게 생각하고 적록색약이 아닌 사람은 다르게 생각하는 상황에서 구역의 개수를 구하는 문제로 BFS 알고리즘과 DFS 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 적록색약이 아닌 경우를 먼저 구하고 이후 원본에서 초록색을 전부 빨간색으로 바꿔서 다시 구하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { private static final int[] dr = {-1, 0, 1, 0}; private static final int[] dc = {0, 1, 0, -1}; pu.. 2025. 1. 23.
[백준] 6593번 - 상범 빌딩 [Java] https://www.acmicpc.net/problem/6593 1.  아이디어 S에서 E로 가는 최단 경로를 찾는 문제로 3차원 배열과 BFS 알고리즘을 활용하면 해결할 수 있다.2. 문제풀이 높이까지 추가된 6방 탐색을 활용해 BFS 알고리즘을 돌리는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final int[] dr = {-1, 0, 1, 0, 0, 0}; private static final int[] dc = {0, 1, 0, -1, 0, 0}; private static final int[] dh = {0, 0, 0, 0, -1, 1}; public sta.. 2025. 1. 23.

티스토리툴바