컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 문제 해결 알고리즘 위상 정렬문제인데 인접리스트를 이중배열로 구현해야한다는 점과 "?"과 "impossible"을 구분해주어야하는 점이 어려웠다. (두 팀의 순서를 바꿀 때 좀 복잡하기 때문에 이중배열이 더 편했다.) q에 원소가 2개 이상이면 "?"를 출력해주고 q에 원소가 없고 방문하지 않은 노드가 있다면 "impossible"을 출력해준다. 2개 이상도 아니고 모든 노드를 방문했다면 ..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 문제였으나 사이클을 유무를 확인해야하는 문제였다. 아래의 링크에 위상 정렬 알고리즘에 대한 자세한 설명이 나와있다. https://kimmessi.tistory.com/207 소스 코드 #include using namespace std; int N, M; bool flag = true; int indegree[1002]; vector g..

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 알고리즘 문제였다. 아래의 링크에 위상 정렬에 대해 자세히 설명 되어 있다. https://kimmessi.tistory.com/207 소스 코드 #include using namespace std; int N; int indegree[502], Time[502]; vector graph[502]; void topologySort(){ vector..

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 문제 해결 알고리즘 전형적인 위상정렬 알고리즘 문제이다. 아래 링크에 자세한 풀이가 나와있다. https://kimmessi.tistory.com/207 [알고리즘] 위상 정렬 (Topology Sort) - BFS 위상 정렬이란? 순서가 정해져있는 작업을 차례로 수행하여야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 사이클이 없는 방향 그래프..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 알고리즘을 활용한 문제이다. 작업 시간이 있는 것이 좀 다른데, 이것은 계속해서 결괏값을 먼저 해야할 작업이 걸린 시간 + 현재 해야할 작업이 걸리는 시간과 계속 비교해주면서 더 큰 쪽을 결괏값에 대입해준다. https://kimmessi.tistory.com/194 [위상 정렬] BOJ 2056 작업 https://www.acmicpc.net/prob..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 알고리즘을 활용한 문제이다. 작업 시간이 있는 것이 좀 다른데, 이것은 계속해서 결괏값을 먼저 해야할 작업이 걸린 시간 + 현재 해야할 작업이 걸리는 시간과 계속 비교해주면서 더 큰 쪽을 결괏값에 대입해준다. 아래의 링크에 위상 정렬 알고리즘에 대한 자세한 설명이 나와있다. https://kimmessi.tistory.com/207 소스 코드 #in..

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 문제이다. 아래의 링크에 위상 정렬 알고리즘에 대한 자세한 설명이 나와있다. https://kimmessi.tistory.com/207 [알고리즘] 위상 정렬 (Topology Sort) - BFS 위상 정렬이란? 순서가 정해져있는 작업을 차례로 수행하여야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순 ki..