본문 바로가기
반응형

분류 전체보기123

백준 2589번 : 보물섬 java 이 문제는 bfs를 이용하여 섬 안에서 가장 먼 거리에 보물을 묻을 때 보물 간의 거리를 구하는 문제입니다. 이 문제를 풀 때는 브루트포스 알고리즘을 사용해야 합니다. 지도의 각 칸을 탐색하면서 탐색한 칸이 땅일 때 연결된 땅들을 전부 탐색하면서 가장 거리가 먼 땅을 찾습니다. 코드를 보면서 조금 더 설명드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int row, col; static char[][] map; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; static int max = 0; public static void main(Strin.. 2022. 6. 24.
백준 1238번 : 파티 java 이 문제는 다익스트라 알고리즘을 이용하여 학생들이 파티를 참가하기 위해 한 마을로 모였다가 다시 자신의 마을로 돌아갈 때 가장 시간이 오래 걸리는 학생의 소요시간을 구하는 문제입니다. 이 문제를 푸는 방법은 2가지가 있습니다. 우선 첫 번째의 방법은 플로이드 와샬 알고리즘을 이용하여 각각의 학생들이 오고 갈 때의 시간을 구하는 방법이 있습니다. 하지만 이 방법을 사용한다면 시간 복잡도가 O(n^3)이 되어 시간이 오래 걸리게 됩니다. 이 문제에서는 플로이드 와샬 알고리즘을 써도 맞다고는 나오지만 N이 더 늘어나면 시간이 메모리를 더 많이 쓰게 되므로 좋은 정답이 아닙니다. 우선 플로이드 와샬 알고리즘으로 이 문제를 풀었을 때를 보여드리겠습니다. import java.io.*; import java.uti.. 2022. 6. 24.
백준 2468번 : 안전 영역 java 이 문제는 배열의 각 칸을 순회하면서 bfs를 이용하여 연결된 안전 영역들을 탐색하는 문제입니다. 연결된 안전 영역들의 개수를 파악하는 문제입니다. 코드를 보면서 추가로 설명드리겠습니다. import java.io.*; import java.util.*; public class Main { static int N, safe = 0; static int minHeight = Integer.MAX_VALUE; static int maxHeight = Integer.MIN_VALUE; static int[][] map; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; public static void main(String[] args) th.. 2022. 6. 23.
백준 2580번 : 스도쿠 java 이 문제는 스도쿠 문제를 백트래킹을 이용하여 푸는 문제입니다. 위와 같은 스도쿠 판이 있다고 가정하겠습니다. 이 스도쿠 판에서 빈칸들을 채우기 위해서는 아래와 같이 가로, 세로, 박스 안을 확인해야 합니다. 이 세 영역에 빈칸에 넣는 수와 같은 수가 존재하지 않아야 빈칸에 수를 삽입할 수 있습니다. 코드를 보면서 이 문제의 풀이에 대해 더 자세히 설명드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int[][] board; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputSt.. 2022. 6. 23.
백준 16234번 : 인구 이동 java 이 문제는 데이터들을 입력 받아서 주변과의 차이가 L 이상, R 이하라면 각각의 셀에 있는 값들을 모두 더해서 평균값으로 만들어주는 알고리즘입니다. 예제 1번을 보시면 이를 더 잘 이해하실 수 있습니다. 코드를 보면서 추가로 설명해드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int N, L, R; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; static int[][] map; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedRe.. 2022. 6. 23.
백준 15655번 : N과 M (6) java 이 문제는 입력 받은 배열을 정렬한 후 자신 이후의 인덱스에 있는 자료들을 M개 만큼 출력하는 문제입니다. 이 문제를 해결하기 위해서는 재귀적으로 함수를 불러오면서 불러온 횟수가 M번이 되면 출력하면 됩니다. 코드를 보시면 쉽게 이해하실 수 있으실 겁니다. import java.io.*; import java.util.*; public class Main { static int N, M; static int[] data; static int[] answer; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String.. 2022. 6. 22.
백준 2252번 : 줄 세우기 java 이 문제는 위상 정렬을 이용하여 그래프를 일차원으로 나타내는 문제입니다. 위상 정렬에 대하여 우선 설명드리겠습니다. 위상 정렬이란 그래프 내에서 순환이 없을 때 순서에 맞게끔 나열하여 한 줄로 그래프 내에 있는 자료들을 정렬하는 것을 의미합니다. 예를 들어 위와 같은 그래프가 있다고 하겠습니다. 이 그래프를 순서에 맞게 정렬해보도록 하겠습니다. 우선 첫 번째 자리에는 자신을 가리키는 노드가 없는 노드가 들어갑니다. 따라서 1과 6을 큐에 삽입해줍니다. 우선 큐에 먼저 삽입된 1번 노드를 먼저 확인하겠습니다. 1번 노드에서 나아간 간선들을 2와 3을 가리키고 있습니다. 또한 2와 3을 가리키는 다른 노드들이 없기 때문에 큐에 2와 3 노드를 삽입해줍니다. 이제 1과 연결된 다른 노드가 없기 때문에 큐의 맨.. 2022. 6. 21.
백준 2636번 : 치즈 java 이 문제는 너비 우선 탐색을 이용하여 다음에 없어질 치즈들을 큐에 저장한 후에 그다음 시간에 모든 치즈들이 사라지면 순회를 종료하는 알고리즘입니다. 이 문제를 풀 때 조심하셔야 하는 점은 밖의 공기와 접한 치즈들만 녹아서 없어진다는 것입니다. 위의 그림에서 없어지는 부분들을 확인해 보시면 안의 공기와 맞닿은 부분들은 녹지 않는데 밖의 공기와 맞닿은 부분들만 녹습니다. 따라서 우리는 밖의 공기와 접해 있는 치즈의 부분들만 큐에 넣은 후 제거해야 한다느 것을 알 수 있습니다. 또한 이 문제를 풀 때 공기와 맞닿은 치즈 부분들을 바로 큐에서 제거하면 안됩니다. 다음 차례에서 모든 치즈들이 사라진다면 남아 있는 치즈들의 개수를 세야 하는데 치즈들을 바로 없애면 이를 할 수 없기 때문입니다. 따라서 저는 이 문제.. 2022. 6. 20.
반응형

티스토리툴바