기맹기 개발 블로그

BOJ 9466 텀 프로젝트 난이도 : 골드 3 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 전략 사이클을 형성하지 않는 노드의 수를 구하면 된다. dfs 등 그래프 탐색으로도 해결할 수 있지만 방문 처리하는게 귀찮아서 위상정렬로 풀었다. 사이클에 포함되는 노드는 위상정렬 중에 방문되지 않는다. 이렇게 사이클에 진입하려고 하면 해당 노드가 진입차수가 0이 될 수 없어서 방문되지 않는다. 따라서 위상정렬하면서 방문된 노드의 개수를 출력하도록 하였다..

BOJ 1766 문제집 난이도 : 골드 2 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 전략 위상정렬 문제이므로 문제집 순서를 그래프로 잘 표현해야 한다. 처음 접근했던 방법은 다음과 같다. 우선 입력을 바탕으로 방향 그래프를 생성한다. (그림에서 검은색 화살표) 그리고 노드 번호를 오름차순으로 탐색하면서 자신보다 높은 번호를 가진 노드를 가리키는 간선을 추가한다. (그림에서 파란색 화살표) 이 때 사이클이 생..

BOJ 3665 최종 순위 난이도 : 골드 1 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 전략 1. 각 팀의 기존 순위를 그래프로 표현 2. 변경된 순위로 간선의 방향을 반대로 변경 3. 위상 정렬을 통해 최종 순위 출력 시행착오 처음에는 위처럼 일방향으로 그래프를 이어줬는데 위 상태에서는 순위 변경에 따라 간선 방향을 변경할 수 없다. 따라서 자신보다 뒷 순위 팀을 모두 가리키도록 그래프를 구성하고, 변경된 순서에 따라 간선 방향..