반응형 SMALL 자바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. [백준] 9663 N-Queen (Java/자바) 문제https://www.acmicpc.net/problem/9663 문제풀이처음에는 map을 2차원 배열로 잡고 무지성으로 Brute Force 방법으로 풀었으나 당연하게도 시간초가 났다.이 문제를 푸는 방법에 대해서는 다른 블로그를 참고하여 풀었는데 그 방법을 보아하니 아래와 같은 로직으로 풀게 되어있었다. (사전지식)Queen 은 상/하/좌/우/대각선으로 마음대로 움직일 수 있다. 따라서 Queen의 상, 하, 좌, 우 (= 다른 말로 Queen이 놓여진 행/열)의 index와 같은 Queen은 무조건 공격 받는다. 그렇기 때문에 map의 크기를 2차원 배열로 사용하지 않고 1차원 배열로 해놓고 map의 index를 열로, map 안의 원소의 값를 행으로 생각하고 문제를 푼다. 1. Queen을 .. 2024. 7. 23. 이전 1 2 다음 반응형 SMALL
