위상정렬

Algorithm/Baekjoon Online Judge
[Java] 백준 2252 (줄 세우기) Gold 2
Problem : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net Approach 위상정렬(Topological Sort) 을 활용하는 기본문제이다. 위상정렬을 구현할 줄 안다면 별다른 처리는 더 필요 없는 문제였다. 일반적인 위상정렬처럼 inDegree 배열을 구성하고, inDegree가 0인 노드들을 큐에 넣고 뽑고를 반복하며 진행한다. Code import java.io.*; import java.util...
→2021.04.22
Algorithm/Baekjoon Online Judge
[Java] 백준 2056 (작업) Gold 4
Problem : https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Approach 기본적인 위상정렬 (Topological Sort) 문제였다. 위상 정렬에서는 선행되어야 하는 것들의 개수를 저장하는 inDegree 배열이 필요하다. 먼저 inDegree[a] 를 a작업이 수행되기까지 선행되어야 하는 작업의 수라고 정의한다. 그렇게 inDegree를 구성하고, inDegree가 0인 것..
→2021.04.20
Algorithm/Baekjoon Online Judge
[Java] 백준 1766 (문제집) Gold 2
Problem : https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net Approach 위상정렬 + PriorityQueue 를 활용한 문제이다. 위상정렬을 알고 있다면 꽤 쉬운 문제이다. 문제를 풀이하는데 있어 순서가 존재하므로 위상정렬을 떠올릴 수 있었다. 또한, 지금 풀 수 있는 문제가 여러개일 때, 번호가 작은 문제부터 풀어야 하므로 우선순위 큐를 생각할 수 있겠다. 입력을 모두 받을 때까지 inDegree 배열..
→2021.04.07
Algorithm/Baekjoon Online Judge
[Java] 백준 1516 (게임 개발) Gold 3
Problem : https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net Approach 어떤 작업을 해야할 때 선행되야 하는 작업이 있다면, 위상정렬도 한번 생각해 보는 것이 좋다. 대개 위와 같은 문제 유형이면, 위상정렬을 사용하는 문제인 것들이 많았다.(개인적인 생각) 이 문제도 마찬가지로 위상정렬로 풀이하였다. 위상정렬의 개념은 설명하지 않겠다. 위상정렬의 기본 구조를 크게 벗어나지 않았고, 응용하는 부분도 없기에 조금의 코드설명만 ..
→2021.03.31
Algorithm/Baekjoon Online Judge
[Java] 백준 1005 (ACM Craft) Gold 3
Problem : https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net Approach 위상정렬(Topological Sort)의 연습문제이다. 위상정렬 자체에 대해서는 간단히 설명하겠다. 알고리즘에서 꽤나 자주 나오는 개념이므로 숙지해두면 좋을 것이다. DAG(Directed Acyclic Graph: 방향성이 있고 싸이클이 없는 그래프)에 순서가 곁들여져 있는 경우, 위상정렬을 사용해 볼 수 있다. 위상정렬에서는 중요한 개념 하나가 있다. ..
→2021.03.28

• 이전
• 1
• 다음