https://www.acmicpc.net/problem/7469 7469번: K번째 수 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. 현정 www.acmicpc.net 노드에 해당 구간에 정렬된 값들이 저장되는 머지 소트 트리를 만들고 특정 구간에서 어떤 숫자 이하의 개수가 몇 개인지 구하는 쿼리를 만들어 이분 탐색을 통해 문제를 해결했다. 코드 #include #include #include using namespace std; int n, m; vector inputs(100001, 0); vector mgstt[400004]; //머지소트트리 vector::it..

https://www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 가장 긴 증가하는 부분 수열 (n log n) 풀이로 가장 긴 오름세를 찾아서 문제를 해결했다. 코드 #include #include #include using namespace std; int tc; int n; vector p; vector check; vector::iterator it; void Pre() { p.clear(); check.clear(); } int main() { cin..

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가 주어진다. ( www.acmicpc.net 유니온 파인드를 이용해 문제를 해결했다. 친구 관계를 유니온 하였는데, 유니온 하면서 해당 그룹의 비용은 더 작은 값으로 하도록 만들어서 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n, m, k; vector cost(10001); vector parent(100..

https://www.acmicpc.net/problem/1649 1649번: 택시 첫 번째 줄에 교차로의 개수인 N(1 n >> m; for (int i = 0; i > u >> v; adj[u].push_back(v); indegree[v]++; } cin >> a >> b >> k; for (int i = 0; i > c_i; c_check[c_i] = 1; } queue q; //(위치, 해당 위치까지 방문한 들려야할 중간 지점의 개수) int start_mid = 0; //시작지점이 들려야할 중간지점일때 if (c_check[a] == 1) start_mid++; mid_max[a] = start_mi..

https://www.acmicpc.net/problem/1777 1777번: 순열복원 순열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄에는 순열 1, 2, …, N에 해당하는 Inversion sequence가 공백으로 구분되어 들어온다. www.acmicpc.net number_check에 숫자의 자리가 채워진 위치는 0으로 체크하고 자리가 채워지지 않은 위치는 1로 체크하여 이것을 합 세그먼트 트리로 만든다. 그리고 큰 숫자부터 자리를 찾아가면서 해당 숫자보다 뒤에 나오면서 해당 숫자보다 작은 수의 개수는 number_check에서 뒤에 1로 채워진 개수가 몇 개인지 확인하는 이분 탐색을 통해 자리를 찾으면서 문제를 해결했다. 코드 #include #include #includ..

https://www.acmicpc.net/problem/17132 17132번: 두더지가 정보섬에 올라온 이유 문제에 제시된 이동을 끝냈을 때, 두더지가 느끼는 만족도의 총합을 출력한다. www.acmicpc.net 간선을 가중치의 내림차순으로 정렬하여 가중치가 큰 것부터 해당 간선의 가중치가 만족도가 되는 경우의 개수를 찾아서 문제를 풀었다. 이때 확인한 간선의 정점들은 유니온 파인드의 유니온을 하고 해당 정점이 속한 그룹의 개수를 저장하여 이용하는 방식을 통해 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n; vector edge; long long result = 0; vector parent(100001); ..