컴퓨터하는 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/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 해결 알고리즘 다익스트라 + 경로 출력해줘야하는 문제. 다익스트라 알고리즘에서 더 값이 적은 경로가 나왔을 때, 해당 위치가 어떤 위치에서 왔는지 기록하는 배열을 만들어서 추적했다. 아래의 링크에 다익스트라 알고리즘에 대한 설명되어있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라 - 선형 탐색..

https://codeforces.com/problemset/problem/1700/A Problem - 1700A - Codeforces codeforces.com 문제 해결 알고리즘 $n \times m$ 배열이 위의 내용처럼 $a_{ij} = (i-1)m + j$이라면, 최소 경로는 맨위의 행과 맨 오른쪽 열의 합을 더해준 값과 같다. 그러므로 각각의 값을 구한 뒤 겹치는 $a_{1m}$값을 빼주면 최소 경로 값이 나온다. 소스 코드 #include #define ll long long int using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; ll n, m, result = 0; w..

https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 문제 해결 알고리즘 전형적인 다익스트라 문제이다. 아래 링크에 다익스트라 알고리즘에 대한 설명이 나와있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라 - 선형 탐색, 우선순위 큐 다익스트라 알고리즘 (Dijkstra's algorithm) 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘 다익스트라 알고리즘은 음의..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 문제 해결 알고리즘 문제에 나온 조건을 응용한 다익스트라 알고리즘 문제이다. 아래의 링크에 다익스트라 알고리즘에 대해 설명되어있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라 - 선형 탐색, 우선순위 큐 다익스트라 알고리즘 (Dijkstra's algorithm) 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고..

골드 1에서 9개월 정도 걸려서 겨우 플레 찍었네요 ㅠㅠ

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/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상정렬 알고리즘 문제였으나 가능하면 쉬운 문제부터 푼다는 조건이 들어가있는 문제이다. 이 문제는 위상정렬할 때 쓰이는 큐를 우선순위 큐로 오름차순 정렬해주면 풀리는 문제였다. 아래는 링크는 위상정렬 알고리즘에 대해 자세히 설명되어있다. https://kimmessi.tistory.com/207 소스 코드 #include using nam..