본문 바로가기
반응형

전체 글124

백준 1504번 : 특정한 최단 경로 java 이 문제는 다익스트라 알고리즘을 이용하여 중간에 정점 v1과 v2를 거쳐 N으로 갈 때의 최단 경로의 길이를 구하는 문제입니다. 이 문제를 풀기 위해서는 우선 정점 1에서 v1과 v2로 갈 때의 최단 경로의 길이를 구해야 합니다. 만약 경로가 존재하지 않을 경우에는 그다음 단계를 진행하지 않아도 됩니다. 1에서 v1으로 가는 경로가 없다고 가정하면 1에서 v2로 가는 최단 경로를 구하고 그 후 v2에서 v1으로 가는 최단 경로를 구해야 합니다. v2와 v1을 모두 거쳐야 하기 때문에 이 경로를 구해줍니다. 그리고 마지막으로 v1에서 N으로 가는 최단 경로를 구한 후 이 3개의 경로의 길이를 더한 값을 출력합니다. 이에 대해서 예제 1번을 예시로 설명드리겠습니다. 위 그림은 예제 1번을 나타낸 그림입니다... 2022. 6. 25.
백준 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.
반응형

티스토리툴바