반응형 분류 전체보기123 백준 14567번 : 선수과목 (Prerequisite) java 이 문제는 위상 정렬을 이용하여 주어진 조건에 맞게 각 과목을 이수하려면 몇 학기가 걸리는지를 구하는 문제입니다. 위상 정렬을 이용하는 방법은 아래 링크를 참고하시면 좋을 것 같습니다. 백준 1516번 : 게임 개발 java 이 문제는 위상 정렬을 이용하여 건물들을 순서대로 완성시키는 알고리즘입니다. 이 문제를 해결하기 위해서는 자신보다 선행되어야 하는 정점들이 걸리는 시간에 지금 정점에서 걸리는 시간 dy-coding.tistory.com import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static int[] parentNum; static int[] answer;.. 2022. 7. 19. 백준 24444번 : 알고리즘 수업 - 너비 우선 탐색 1 java 이 문제는 bfs를 이용하여 정점들을 탐색하면서 각 정점별로 호출된 순서를 출력하는 문제입니다. 이 문제의 예제를 통해 설명드리도록 하겠습니다. 이 문제의 예제를 그래프로 나타내면 다음과 같습니다. 시작 정점이 1번이니 여기서 시작하여 bfs를 순서대로 실행하는 모습을 보여드리겠습니다. bfs를 통해서 순서를 타고 내려갈 때 정점의 수가 적은 순으로 내려가니 그다음은 2번 노드와 4번 노드 중에서 2번 노드로 갑니다. 이제 2번 노드를 탐색했으니 1번 노드와 연결되어 있던 4번 노드를 탐색해줍니다. 이제 2번 노드와 연결되어 있던 3번 정점을 탐색해줍니다. 5번 정점을 갈 수 없으므로 0을 넣어줍니다. 다음과 같은 알고리즘으로 이 문제를 해결하실 수 있습니다. import java.io.*; import.. 2022. 7. 17. 백준 10282번 : 해킹 java 이 문제는 다익스트라 알고리즘을 이용하여 시작 정점에서 시작되어 컴퓨터가 감염되는 시간과 몇 대가 감염되었는지 출력하는 문제입니다. 이 문제에서는 테스트 케이스마다 컴퓨터간의 의존성 관계를 입력받은 후 다익스트라 알고리즘을 각각 실행하여 어느 컴퓨터까지 감염되었는지 확인합니다. 다익스트라 알고리즘을 활용할 줄 알면 조건에 따라 쉽게 해결할 수 있는 문제입니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri.. 2022. 7. 15. 백준 2056번 : 작업 java 이 문제는 위상 정렬을 이용하여 선행 관계에 있는 작업들을 먼저 한 후 그다음 작업들을 할 때 총 걸리는 시간이 얼마인지 구하는 문제입니다. 이 문제는 아래의 링크에 있는 문제와 푸는 방식이 동일하니 풀이는 아래의 링크를 참고해주시기 바랍니다. 백준 1516번 : 게임 개발 java 이 문제는 위상 정렬을 이용하여 건물들을 순서대로 완성시키는 알고리즘입니다. 이 문제를 해결하기 위해서는 자신보다 선행되어야 하는 정점들이 걸리는 시간에 지금 정점에서 걸리는 시간 dy-coding.tistory.com import java.io.*; import java.util.*; public class Main { static int N; static int[] time; static int[] parentNum; s.. 2022. 7. 14. 백준 1516번 : 게임 개발 java 이 문제는 위상 정렬을 이용하여 건물들을 순서대로 완성시키는 알고리즘입니다. 이 문제를 해결하기 위해서는 자신보다 선행되어야 하는 정점들이 걸리는 시간에 지금 정점에서 걸리는 시간을 더하면 됩니다. 이에 대해서 그림을 통해 설명드리도록 하겠습니다. 예제 1번의 그래프는 다음과 같은 형태입니다. 화살표의 시작점이 선행되어야 하는 정점이고 끝점이 그 후 실행 가능한 정점입니다. 이를 표로 나타내면 아래와 같습니다. 이 표에서 time은 각각의 정점을 실행하는 데에 걸리는 시간, answer은 그 정점이 실행되는 데에 총 걸리는 시간, parentNum을 선행되어야 하는 정점의 수입니다. 이제 건물을 짓기를 시작하도록 하겠습니다. 우선 처음에는 선행해야하는 건물이 없는 1번 정점을 먼저 건설합니다. 그럼 이제.. 2022. 7. 13. 백준 6118번 : 숨바꼭질 java 이 문제는 1번 정점에서 탐색을 시작하여 1번 정점에서 다른 정점에 이르기까지 얼마의 시간이 걸리는지 찾는 문제입니다. 위의 사진은 이 문제에서 힌트로 나와 있는 그림입니다. 이 그림과 같이 1번 정점을 기준으로 가장 멀리 떨어져 있는 정점들을 찾으면 됩니다. 이 그림에서는 4, 5, 6이 1에서 거리가 2로 가장 먼 정점들입니다. 그리고 거리가 같을 때는 정점의 번호가 가장 작은 정점에 숨으므로 숨어야 하는 정점은 4이고 거리는 2, 이 헛간과 같은 거리에 있는 헛간의 수는 3개입니다. import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static boolean[] .. 2022. 7. 12. 백준 2252번 : 음악프로그램 java 이 문제는 위상 정렬을 이용하여 그래프 구조로 되어 있는 자료들을 배열의 형태로 나타내는 문제입니다. 위상 정렬에 관련된 내용들은 아래에 있는 링크를 참고하시면 이해하실 수 있으실 겁니다. 백준 2252번 : 줄 세우기 java 이 문제는 위상 정렬을 이용하여 그래프를 일차원으로 나타내는 문제입니다. 위상 정렬에 대하여 우선 설명드리겠습니다. 위상 정렬이란 그래프 내에서 순환이 없을 때 순서에 맞게끔 나열하여 dy-coding.tistory.com 이 문제는 위의 문제와 거의 유사한 형태의 문제입니다. 위상 정렬에 대한 풀이만 이해하시면 위의 문제를 해결하실 수 있으실 겁니다. import java.io.*; import java.util.*; public class Main { static int N;.. 2022. 7. 11. 백준 1743번 : 음식물 피하기 java 이 문제는 각각의 칸들을 순회하면서 dfs 또는 bfs를 하여 음식물이 떨어진 구간의 크기가 가장 큰 구간의 크기를 출력하면 되는 문제입니다. import java.io.*; import java.util.*; public class Main { static int R, C, max = Integer.MIN_VALUE; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; static int[][] map; static boolean[][] visited; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new In.. 2022. 7. 10. 이전 1 2 3 4 5 6 7 8 ··· 16 다음 반응형
