onaeonae1

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 문제 설명 두 사람의 키를 비교한 관계들이 쭉 주어질 때 (가능한) 키 순서를 출력하면 되는 문제 문제 풀이 -그래프에서 정해진 노드끼리의 간선등 정해진 순서가 있을 때, 이를 위반하지 않으면서 그래프 전체의 노드를 방문하는 경우를 가져오는게 위상정렬 문제의 특징이다. -위의 문제는 기본적인 위상정렬 문제라서 크게 변형할 것이 없었다. 바로 연결 관계 받고, 위상 정렬 구현해..

www.acmicpc.net/problem/3665 3665번: 최종 순위 문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 �� www.acmicpc.net 문제를 제대로 해석하지 못해서 좀 고생했다. 문제의 조건을 풀어서 설명하면 다음과 같다. 기존의 순서가 주어지고, 이후 상대적인 순서의 변경이 주어질 때, 변경된 순서대로 출력 만약 불가능하다면, IMPOSSIBLE 출력 처음에 주어진 순서대로 연결해주고, 이후 변경된 순서를 적용시켜서 연결, 진입차수를 수정해주면 된다. 처음 연결에서 인접행렬을 짜듯이 하나하나 연결을 해줘야 하는게 중요하다. 예를 ..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 이번에도 위상정렬을 쓰는 문제다. 위상정렬을 쓰는 문제들은 그래프에서 순서가 주어지는데, 이 문제에서는 하나의 조건이 더 추가된다. 일단 문제를 풀어 써보자. 1~N까지 총 N개의 문제들로 구성된 문제집이 있다. 1이 가장 쉽고, N이 가장 어렵다.(=번호가 낮을 수록 쉬운 문제이다.) 그리고 주어지는 조건은 다음과 같다. N개의 문제를 모두 풀어야 한다. 주어진 순..