반응형 SMALL 문제풀이/백준19 [백준] 18808번: 스티커 붙이기 (Java/자바) 문제https://www.acmicpc.net/problem/18808문제풀이⭐ 가장 중요한 것 은 Rotation을 어떻게 할 것 인지가 중요하다. 나는 아래와 같이 그림을 그리면서 로테이션 했을 때 (y, x) 좌표가 어떤식으로 변화하는지 확인하였다. 이 과정에서 Rotation을 구현할 수 있었고 그 외에는 시뮬레이션을 돌려가며 순서대로 구현하면 문제없이 풀 수 있다. 소스코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;import java.util... 2024. 8. 7. ⭐ [백준] 7569번: 토마토 (Java/자바) 문제https://www.acmicpc.net/problem/7569 문제풀이전형적인 BFS 문제이다. 익지 않은 토마토를 Queue에 담고 순차적으로 높게, 낮게, 상, 하, 좌, 우 방향으로 움직이며 탐색하면 되는 문제이다. 아래와 같은 조건을 주의해야 한다. 1. 토마토가 모두 익지 않을 때는 `0` 을 출력한다. (토마토가 모두 익지 않는 경우가 존재한다.)2. 상자의 일부에는 토마토가 존재하지 않을 수 있다. 소스코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;import java.uti.. 2024. 8. 1. [백준] 1916번: 최소비용 구하기 (Java/자바) 문제https://www.acmicpc.net/problem/1916 문제풀이일반적인 다익스트라 문제이다. 오랜만에 풀어보니 어려움이 있었다.. 그래서 손으로 적어가면서 풀었는데 좀 많이 틀렸다... 내가 틀린 이유는 아래와 같은 부분을 고려하지 못하여서 틀렸다. 1. 출발지점과 끝지점이 같은 버스가 여러 대 올 수 있다. (이때는 최소값으로 갱신 또는 유지)2. Integer.MAX_VALUE 를 사용하여 풀려고 했는데 Overflow 문제가 있었다.3. 버스의 번호는 1~N 까지 이므로 초기화 해줄 때 또는 for문 돌 때 주의해야한다.소스코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList.. 2024. 7. 30. [백준] 14888번: 연산자 끼워넣기 (Java/자바) 문제https://www.acmicpc.net/problem/14888 문제풀이기초 구현 문제이다. 사실 이러한 형식으로 나오는 문제 중에서는 단순 구현 보다는 DP 문제가 더 많은데 난이도가 쉬운 문제로 출제가 되면서 단순 구현으로도 풀 수 있는 난이도의 문제로 출제 되었다. 해당 문제는 순서대로 읽어보고 차례대로 구현하면 별 이상 없이 바로 맞출 수 있는 문제이다. 소스코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static int N.. 2024. 7. 28. [백준] 11726번: 2xn 타일링 (Java/자바) 문제https://www.acmicpc.net/problem/11726 문제풀이전형적인 DP 문제이다. 이 문제는 처음에 봤을 때 완전 탐색으로 풀어야하나? 이렇게 고민되기도 하지만, 그렇게 된다면 구현 자체도 복잡할뿐만 아니라 2의 N승까지의 복잡도를 갖기 때문에 시간내에 풀 수 없게된다. 천천히 생각해보면 N = 1, N = 2, N = 3, ... 일때의 상황을 그려보고 점화식으로 풀이가 가능한 형식임을 눈치채야한다. 점화식은 dp[N] = dp[N-1] + dp [N-2] 이다.dp[1] = 1 // N == 1 일 때 가능한 조합은 1가지 뿐이다.dp[2] = 2 // N == 2 일 때 가능한 조합은 2가지 이다. (2x1 을 2개 쌓거나, 1x2를 2개 쌓거나)dp[3] = 3 // N ==.. 2024. 7. 28. ⭐ [백준] 11053번: 가장 긴 증가하는 부분 수열 (Java/자바) 문제https://www.acmicpc.net/problem/11053 문제풀이가장 베이직한 DP 문제라고 할 수 있다. 일반적으로 DP는 이전 값을 `기억` 하는데 초점을 맞추면 된다.memoization alogorithm 이라고 할 수 있는데 위 문제가 가장 기초가 되는 문제이다. 예제를 기준으로 설명하자면 아래와 같다. 1. N의 크기를 갖는 dp 배열을 생성한다.2. dp는 0~N 까지의 index의 수열들이 갖는 최대 부분 수열을 저장할 용도이다.3. dp는 초기에는 값을 업데이트 하지 않았기 때문에 자기 자신만을 수열로 갖는 상태이므로 1로 초기화 시켜준다.4. [ 10, 20, 10, 30, 20, 50 ] 수열의 0 index에서 부터 N번째 index까지 순차적으로 탐색한다.5. 탐.. 2024. 7. 24. 이전 1 2 3 4 다음 반응형 SMALL
