https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이과정 dp와 위상 정렬을 같이 쓰는 문제이며 1005 ACM Craft 문제와 비슷한 문제이다. 이처럼 위상정렬과 dp가 같이 쓰이는 문제가 많은 것 같다. 풀이 과정은 1005번 문제와 같지만, 처음에 입력문에서 v를 푸시하는 과정에서 반대로 푸시를 해 고생을 먹었던 문제이다. 몇 번 노드에 몇 번 노드를 푸시해줄 것인지 방향을 잘 생각해서 입력받아야 한다. 도착점이 정해져있지 않으..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이과정 이 문제는 조건 3개를 잘 기억해야 한다. 1. N개의 문제는 모두 풀어야 한다. 2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 3. 가능하면 쉬운 문제부터 풀어야 한다. 문제를 읽어보면 1번 문제가 쉬운 문제이고 N번 문제가 가장 어려운 문제라고 하였으니 우선순위 큐를 떠올려 봐야한다. 원래 우선순위..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이과정 이 문제는 dp와 위상 정렬을 같이 쓰는 문제이다. res배열이 dp이고, 각 지점을 지날 때 가장 오래 걸리는 시간을 넣는 배열이다. #include #include #include #include using namespace std; int T, N, K, x, y, W; int build[1001]; int indegree[1001]; // 진입차수 int res[1001]; ..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 풀이과정 일단 위치 입력 받은 것을 sort함수로 정렬해준다. 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야한다고 했으니 loc[i] - start에 1씩 더해준다. 그 값이 테이프의 길이보다 더 클 경우 개수를 카운트해주며 시작지점(start)을 loc[i]로 업데이트해준다. #include #include using namespace std; int main()..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이과정 크루스칼 알고리즘의 대표적인 문제다. 두 개의 마을로 나눠야 하니까 마지막 간선(가장 가중치가 큰 간선) 을 안 더해주면 된다. #include #include #include using namespace std; int N, M, A, B, C; int parent[100001]; vector v; int getParent(int x) { if (x..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이과정 크루스칼 알고리즘의 대표적인 문제이다. 연결된 노드의 개수가 정점의 개수 -1개가 되면 노드 연결을 끝내고, 가중치의 합을 출력하면 된다. #include #include #include using namespace std; int V, E, A, B, C; int parent[10001]; vector graph; int getParent(..

https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 풀이과정 어려운 문제인 줄 알았지만, 다익스트라에서 1개의 조건만 더 추가하면 되는 기본 문제였다. 상대의 시야를 num 배열에 담고 0이면 안 보이는 것, 1이면 보이는 것으로 해석한다. 상대의 시야에 걸리는 곳을 지나칠 수 없으니까 num이 1일 경우에는 continue를 이용해서 그 분기점을 넘어가도록 구현했다. #include #include #include #i..

https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 브론즈 5문제이지만, 파이썬이나 자바로 풀지 않을 경우 난이도가 상승하는 문제다. 최대 10000 자리까지 될 수 있기 때문에 string으로 입력을 받아준다. 문자열의 길이를 비교해 s1이 항상 크게 해주며 두 문자열을 각각 int 배열에 거꾸로 넣어준다. 각 자리의 수를 더한 것을 sum에 넣고 만약 10이 넘어간다면 다음 자리는 올림을 해준 뒤, sum은 10을 빼주며 res 벡터에 넣는다. #include #include #include #include using namespace std; int ..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이과정 이 문제는 벨만포드의 대표적인 기본 문제이다. 그 이유는 타임머신으로 시간을 되돌아가는 경우가 있으므로 가중치가 음수가 될 수 있기 때문이다. 가중치에 음수가 있다면 다익스트라가 아닌, 벨만포드 알고리즘을 생각해야한다. 문제에 있는 '시간을 무한히 오래전으로 되돌릴 수 있다면'이라는 말은 '음수 사이클이 존재한다면'이라는 뜻이다..

https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 풀이과정 문제를 잘 읽어야한다. 위쪽을 바깥쪽, 아래쪽을 안쪽이라고 생각한다. 0이면 전류가 잘 통하는 흰색이고, 1이면 전류가 통하지 않는 검은색 격자이다. 01이 붙어서 입력되므로 scanf("%1d")를 사용해서 입력 받아준다. 첫번째 줄이고, 전류가 통하는 0일 때 queue에 push를 해주며 방문 표시를 한다. bfs 과정에서는 전류가 통하지 않는 1..