GitHubSeob

문제 https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 문제풀이 크루스칼 알고리즘으로 풀었다. 구조체를 선언하여 섬 1, 섬 2, 무게 제한을 변수로 둔다. 부모를 찾는 find, 두 노드 같은 사이클로 만드는 Union, 두 노드가 같은 사이클인지를 판별하는 isUnion 함수를 구현한다. 모든 입력을 다 받았으면, 정렬을 해야 한다. 가장 작은 길이로 시작점과 도착점을 연결하는 것이 아닌, 최대 개수를..

문제 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 문제풀이 다른 사람들의 풀이보다 벡터를 더 선언한 것 같다.. 입력값들을 저장하는 input, Y 부품을 만들기 위해 필요한 X의 개수를 저장하는 ingr 벡터, ingr[Y][X]=K; 기본 부품인지 나타내는 bool형 벡터 isBase, 들어오는 간선의 개수를 알려주는 indegree 벡터를 선언했다. for (int idx = 0; idx < M; ++idx)..

문제 https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net 문제풀이 입력되는 여러 가지 형태의 나무이다. 나무는 가지 없이 기둥만 있을 수 있다. 나무의 가지가 여러 개 있을 경우 가장 긴 가지의 길이만 필요하다. 입력되는 노드 두 개는 누가 부모인지 모른다. 따라서 node1의 트리와 node2의 트리의 각각 node를 추가해야 한다...

문제 https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 문제풀이 주어진 조건을 통해 트리를 구성하고 노드의 번호 K의 부모노드, 조상 노드(부모의 부모)를 구해 K의 형제 노드를 제외한 손자 노드를 구하면 된다. 숫자는 연속으로 주어지지 않으므로 (쓰지 않는 숫자가 있음) map을 이용하여 트리를 구성했다. unordered_maptree; unordered_mapparent_map; 총 두 개의 map을 구성했다. tre..

문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제풀이 위상정렬 + 우선순위 큐 문제이다. 먼저 풀어야 되는 문제가 있으면 먼저 풀어야 한다. 현재 풀 수 있는 문제가 여러 개라면 번호가 낮은 문제 먼저 풀어야 한다. 위상정렬에서 queue를 쓰는 대신 priority_queue를 사용하면 문제를 쉽게 해결할 수 있다. 코드 #include using namespace std; priority_queuepq..

문제 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 문제풀이 위상정렬을 이용하여 풀었다. 진입차수 벡터를 만들어 진입차수가 0인 노드를 큐에 집어넣는다. 큐에서 pop을 하면서 해당 노드에서 다른 노드로 가는 간선들의 개수를 제거한다. 제거하는 도중, 다른 노드의 진입 차수가 0인 다른 노드가 있으면 큐에 집어넣는다. 노드 개수만큼 반복이 되지 않으면 사이클이 존재한다는 의미인데, 문제에서 A가 B앞..

문제 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 문제풀이 트라이 문제이다. 입력으로는 알파벳 대문자로만 이루어진 string이 들어온다. 트라이는 map을 이용하여 자녀 트라이를, 깊이를 나타내는 depth, 문자열의 끝 여부를 나타내는 isEnd로 구성하였다. void insert(vector& v) { Trie* now = this; for (int idx = 0; idx < v.size(); ++idx) { if (..

문제 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 문제풀이 가장 작은 수 + 그다음 가장 작은 수를 더한다. 파일이 하나가 남을 때까지 반복만 하면 된다. 우선순위 큐를 이용해서 가장 작은 수가 top부분에 오도록 하면 편하다. 파일을 입력받고, 바로 우선순위 큐에 push 한다. 입력이 끝나면 우선순위 큐에 파일이 하나 남을 때까지 파일을 두 개씩 꺼내 더한 값을 다시 큐에 push 한다. 합칠 때 필요한 최소비용을 구해야 하므로 답 ..

문제 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 문제풀이 다 풀고 다른 분들의 풀이를 봤는데 간단하게 풀으셨다... 이런 풀이도 있다 참고만 하시는 걸로... 마을 1부터 마을 N까지 탐색하면서 마을에 도착하면 내릴 수 있는 박스 다 내리고, 박스를 싣는다. 박스를 실을 때는 최대 용량보다 적게 싣는다. 만약 용량을 넘어서면 이전에 실은 박스 중에서 도착 마을이, 이번에 실을 박스의 도착지 보다 먼 마을이 있으면, 박스..