https://www.acmicpc.net/problem/15809 15809번: 전국시대 첫 번째 줄에 국가의 수를 나타내는 N과 기록의 수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 두 번째 줄 부터 N개의 줄에 걸쳐 i번째 국가의 병력 Ai (1 ≤ i ≤ N)가 자연수로 주어진다. (1 ≤ Ai ≤ 10,000) 다 www.acmicpc.net 풀이과정 #include #include #include using namespace std; int N, M, op, P, Q; int parent[100001], res[100001]; int getParent(int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이과정 이 문제는 이분 탐색, BFS, 유니온 파인드 3개의 알고리즘이 섞인 문제여서 매우 어려웠던 문제이다. #include #include #include #include #include using namespace std; int n, m, A, B, cost, s, e; bool c[10001]; vector v[10001]; b..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이과정 이 문제는 유니온 파인드와 map 알고리즘이 섞인 문제이다. 유니온 파인드 알고리즘을 하려면, 처음에 parent 배열에 각자 자신의 번호로 초기화시켜준다. 한 줄에 2명씩 입력되므로 최대 노드 개수는 2 * F 개가 된다. 입력을 받을 때, 만약 map.count가 0이라면 idx를 넣어주고 1씩 플러스 해준다. 그다음 unionParent 함수를 실행하고, 다른 집합일 경우..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이과정 bool 함수의 장점을 느꼈던 문제이다. #include #include #include using namespace std; int n, m, x, y; int parent[500001]; // 부모 노드를 찾는 함수 int getParent(int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent[x])..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 풀이과정 연결되어 있는 노드들 중에 친구비가 작은 친구가 있다면 부모 노드를 바꿔준다. #include #include #include using namespace std; int N, M, k, v, w; int f[10001], parent[10001]; // 부모 노드를 찾는 함수 int getParent(int x) { i..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이과정 1이면 도시들이 연결된 것을 의미하므로 unionParent(i, j) 함수를 실행시켜준다. 그럼 연결된 도시들은 가장 작은 부모 노드를 가지고 있을 것이다. 여행 계획에 있는 도시들을 두 개씩 findParent에 넣어보고 만약에 다른 것이 있다면 연결되지 않은 도시라는 뜻이므로 res를 false로 변경한다. #include #include #include using namespace..

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/1956  1956번: 운동첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의www.acmicpc.net 풀이과정사이클이 생기는 부분의 최소합을 구하면 되는 문제이다.   i == j일 때는 continue 해주고, arr[i][j] + arr[j][i]일 때의 최솟값을 구하면 된다.   만약 res가 INF일 경우는, 사이클이 되는 곳이 한 곳도 없으므로 -1을 출력해준다. #include #include #include using namespace std;int V..

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이과정 예전에 다익스트라 + 플로이드 와샬 문제를 푼 적이 있어서 비슷할 거라고 생각했다. 그러나 생각해야될 것이 많아서 시간이 오래 걸린 문제였다..! 처음에 풀었던 방식은 경유지를 지나면 res배열에 담아주는 방식이다. (2번째 코드) 그러나 이렇게 되면 1행 6열은 1 -> 2 -> 5 -> 6 두개의 경유지를 거치게 되어 첫번째 경유지 2가 아닌, 두번째 경유지인 5를 출력하게 되었다. 최초로 거..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 풀이과정 예전에 풀었던 플로이드 와샬의 백준 키 순서와 비슷한 문제였다. 키 순서 문제 참고하기 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 처음에 입력을 받자마자 num[x][y] = 1, ..