본문 바로가기

문제풀이/백준83

[JAVA] BOJ 백준 1062번 - 가르침 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 2. 내가 푼 방법 읽을 수 있는 단어의 최대 값을 구해야 하기 때문에, 완전탐색을 이용했다. 먼저 처음에 입력을 받을 때 시작 글자 "anti"와 끝 글자 "tica"를 replaceAll로 없앴기 때문에, 완전 탐색이 이뤄질 필요가 없는 케이스들을 바로 리턴해주었다. for (int i = 0; i < N; i++) { arr.. 2023. 11. 24.
[JAVA] BOJ 백준 1655번 - 가운데를 말해요 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 2. 내가 푼 방법 가운데 값을 찾기 위해 두 개의 우선순위 큐를 이용했다. 먼저 bigger는 max 값이 가장 먼저 나와야 하므로 내림차순으로 된 우선순위 큐이고, smaller는 min 값이 가장 먼저 나와야하므로 오름차순으로 된 우선순위 큐이다. 전체적인 그림은 bigger와 smaller를 이었을 때 가운데로 값.. 2023. 11. 22.
[JAVA] BOJ 백준 2098번 - 외판원 순회 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 내가 푼 방법 비트마스크를 이용한 DP 알고리즘 문제이다. TSP 알고리즘을 몰랐기 때문에 다른 분들의 풀이를 참고했다. 이미 방문한 적 있는 노드를 저장하기 위해 int[][] dp = new int[N][(1 2023. 11. 10.
[JAVA] BOJ 백준 1525번 - 퍼즐 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 2. 내가 푼 방법 메모리가 32MB인게 제일 먼저 보여서 방문한 노드를 확인하기 위한 boolean[] visit = new boolean[876543210]; 에 대한 선언을 시도해 봤는데 실패했다. 따라서 다른 분들의 풀이를 통해 Map 자료구조를 이용하는 것을 참고했다. 나는 PriorityQueue를 사용했는데, 그래서 Set을 통해 이미 방문한 적 있는 노드인지 확인했다. 어차피 최소 이동 횟수를 가진 .. 2023. 11. 9.
[JAVA] BOJ 백준 1039번 - 교환 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/1039 2. 내가 푼 방법 DFS 알고리즘을 이용해 푼 문제이다. 하지만 우리가 완전탐색을 진행할 때 중요한 부분이 이미 방문한 노드(숫자) 일 경우에는 다시 방문하지 않는 가지치기가 중요하다. 따라서 이차원 배열을 통해 방문한 숫자인지 확인해주는 것이 필요했다. 또한 맨 앞자리가 0이 되면 안 되는 것이었으므로 숫자의 길이가 달라질 경우에는 바로 리턴을 할 수 있도록 해주었다. public static void dfs(int num, int cnt) { if (String.valueOf(num).length() != String.valueOf(N).length()) return; if.. 2023. 11. 9.
[JAVA] BOJ 백준 2133번 - 타일 채우기 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/1726 2. 내가 푼 방법 BFS 알고리즘 문제이다. 이때 3차원 boolean 배열을 이용해 이미 방문했던 곳을 다시 방문하지 않도록 구현을 했다. 로봇이 이동할 때 궤도가 깔리지 않은 부분(1)을 통과해 지나가지 못하므로 직진 명령을 수행할 때만 주의하면 된다. 그래서 아래처럼 첫 번째 칸, 두 번째 칸, 세 번째 칸을 이동하다가 1을 만나면 break; 로 for문을 빠져나왔다. public static void straight(int x, int y, int d, int cnt, Queue queue) { int[] dx = new int[]{0, 0, 0, 1, -1}; int.. 2023. 11. 2.

티스토리툴바