자료구조

[백준 2696] 중앙값 구하기 (C++)

2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 일단 처음에 들어오는 값은 반드시 최초의 중앙값이고 최초의 기준값이 된다. 그리고 앞으로 들어오는 값을 현재 기준과 비교해서 기준보다 크다면 최소 힙에, 기준보다 작다면 최대 힙에 넣어준다. 만약 지금까지 입력받은 수가 짝수라면 넘어간다. 하지만 홀수라면 현재 기준값이 중앙값이 되기 위해서는 최소 힙과 최대 힙에 들어있는 원소의 수가 서로 같아야 한다. 코드 : 만약 최소 힙의 수가 더 많다면 최소 힙에서 최상단 원소를 중앙값으로 둘..

힙 정렬(heap sort) <priority queue> C++

min heap 구현 heap[i]의 값은 heap[i * 2] 와 heap[i*2 + 1]의 사이에 있다 BST(이진 탐색 트리)구조를 기반으로 한다 STL의 priority queue를 사용하면 되므로 직접 구현할 일은 없겠지만 heap 자료구조를 직접 구현해 본다는 점에서 의미있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include using namespace std; vector heap; void push_heap(vector& heap, int newvalue){ heap.push_back(newvalue); int idx = he..

[백준 17298 17299] 오큰수 , 오등큰수 C++

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 자료구조, 스택 문제 1. 문제풀이 아이디어 N이 최대 1,000,000이므로 단순히 2중 for문으로 해결하는건 시간제한에 걸리게 된다. (N이 최대 5,000 정도면 가능할듯..) (1) 오큰수 1. 스택이 비어있을때 지금 보는 배열의 원소와 원..

Minimum Spanning Tree (MST) - Kruskal

크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기 모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다. 유니온 파인드(Union-Find)에 대한 이해 8할 Edge 구조체 설계 2할? find_topnode() 를 통해서 현재 정점(Vertax)의 최상단 노드(부모노드) 를 알 수 있다. Node[Vertax]의 값이 음수이면 Vertax가 부모노드임을 의미한다 is_cycle()을 통해서 a와 b 정점이 서로 같은 노드인지 확인한다(find_topnode() 사용) Union_node()를 통해서 a 와 b정점을 하나로 병합한다 a, b정점의 부모 노드가 가지는 값은 항상 음수이다. 값이 더 작을수록 더 많은..