www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 최솟값 세그먼트 트리와 최댓값 세그먼트 트리를 만들어서 문제를 해결했다. 코드 #include #include #include using namespace std; int n, m; vector maxsgmtt; vector minsgmtt; vector input_data; int Make_minsgmtt(int here, int range_left, int range_r..

www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 포장할 수 있는 도로의 개수를 스킵할 수 있는 도로의 개수라고 생각을 했다. 다익스트라를 이용해서 문제를 해결하였는데, result[위치][앞으로 포장할 수 있는 도로] = 최소 시간을 저장하였고, pq에 (-비용,(위치,앞으로 포장할 수 있는 도로))를 저장하였다. 그리고 다익스트라를 진행하며 포장할 수 있는 도로의 개수가 있을 때는 현재 here-there 도로 포장 하는..

www.acmicpc.net/problem/2848 2848번: 알고스팟어 첫째 줄에 알고스팟어의 알파벳 순서를 출력한다. 만약, 올바른 순서가 없다면 "!"를, 가능한 순서가 한 개 이상이라면 "?"를 출력한다. www.acmicpc.net 각각 앞뒤 단어를 비교하여 다른 부분을 판단하여 그래프를 만들고, 만들어진 그래프를 이용해 위상 정렬을 하여 문제를 해결하였다. 코드 #include #include #include #include #include #include #include #include using namespace std; int n; set all_a; set::iterator it; vector adj[26]; vector indegree(26, 0); vector input; int ..

www.acmicpc.net/problem/2637 2637번: 장난감조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net x를 만드는데 y가 k개 필요하다면 x에서 y로 가는 그래프 연결을 k개 만들고, n에서부터 탐색을 하여 탐색하는 부품이 기본 부품에 도달했을 때 그 부품을 체크한 백터를 반환하였다. cache를 사용해 같은 부품에 대해서 중복된 연산을 하지 않았다. 코드 #include #include #include using namespace std; int n; int m; vector adj[..

www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 다익스트라 알고리즘을 이용하였는데, result[위치][비용] = 최소 소요시간을 저장하였고, 우선순위 큐에는 ((-소요시간, 비용), 위치)를 저장해서 문제를 풀었다. 다익스트라 알고리즘 중간에 해당 지역에서 비용이 M을 초과했다면 그 경로는 더 이상 탐색하지 않았다. 코드 #include #include #include #include #include using name..

www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net map을 활용한 유니온 파인드를 통해 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int tc; int f; map parent; map::iterator it; map rank_size; map num; void Pre() { parent.clear(); rank_size.clear(); num.clea..