알고리즘/위상정렬3 [백준 2623] 음악프로그램 / 자바 / 위상정렬 #문제 레벨: G3알고리즘: 위상정렬 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2623 #문제 풀이 위상정렬이란 순서가 정혀져 있는 작업을 순서를 정해주는 작업을 뜻한다.코드는 큐로 구현된다. 방향성이 있는 선들을 하나 씩 끊어주는 느낌으로 구현하면된다. 그리고 선이 다 끊어진 노드들은 결과에 포함시킨다. 글보다는 코드로 보는 것이 이해가 더 쉬울 것이다. 아래를 참조바란다.#풀이 코드 import java.util.*;import java.io.*;public class Main { static ArrayList[] graph; static int[] inDegree; static int N, M.. 2024. 9. 6. [백준] 줄 세우기 / 자바 문제 레벨: G3알고리즘: 위상정렬 + 풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/22521 번째 시도 가장 단순하게 구현을 하면 학생수만큼의 길이를 가진 배열을 만들고 문제에서 조건이 주어질 때마다 배열의 원소들의 위치를 바꿔주면 됩니다. 그러나 이렇게 하면 시간 복잡도에서 당연히 초과 판정을 받게 될 겁니다. 그렇기 때문에 알고리즘을 써야 하고 이때 사용할 수 있는 알고리즘은 위상 정렬(Topological Sort)이 있습니다. 위상 정렬(Topological Sort)은 그래프에서 선후관계 조건이 있을 때 이를 고려해서 노드의 순서를 정렬할 수 있습니다. (위상정렬은 순환그래프가 포함될 시 사용하지 못한다.) import ja.. 2024. 5. 24. [백준] ACM Craft/자바 문제 레벨: G3알고리즘: 위상정렬 + DP 풀이시간: 2시간힌트 참조 유무: 유https://www.acmicpc.net/problem/10051 번째 시도 입력을 받을 때마다 해당번호의 짓는 시간을 업데이트를 해줬다.결과는 실패이유는 입력 순서가 차례대로일거라고 가정했기 때문이다.import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.. 2024. 5. 16. 이전 1 다음
