기맹기 개발 블로그

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

BOJ 1005 ACM Craft 난이도 : 골드 3 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 전략 단순 위상정렬해서 순서만 중요한 것이 아니라 소요시간을 계산해야 한다. 이는 다음 노드 탐색 과정에서 메모이제이션을 이용하여 최댓값을 저장하는 방식을 사용했다. 단순히 값을 저장하면 되는 것처럼 보이지만, 여러 경로가 합쳐질 때는 최댓값을 이용하여야 결과를 얻을 수 있다. 시행착오 메모이제이션을 큐에서 꺼낸 위치에서 실행했는데, 이미..

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. 위상 정렬을 통해 최종 순위 출력 시행착오 처음에는 위처럼 일방향으로 그래프를 이어줬는데 위 상태에서는 순위 변경에 따라 간선 방향을 변경할 수 없다. 따라서 자신보다 뒷 순위 팀을 모두 가리키도록 그래프를 구성하고, 변경된 순서에 따라 간선 방향..

BOJ 2252 줄 세우기 난이도 : 골드 3 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 전략 문제 이름만 봤을 때는 7568 덩치 랑 비슷해보이지만, 자세히 읽어보면 그래프 문제라는 것을 알 수 있다. 일부 학생들에 대해서만 키 비교가 있고 이에 따라 순서가 정해지므로 방향 그래프인데 물리적인 키를 서로 비교한 것이기 때문에 사이클이 생길 수 없는 조건이다. 이는 위상 정렬로 간단하게 풀 수 있..