1. 최소 힙 (1927)
1) 문제
문제 설명
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.
배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
2) 문제 분석 및 풀이
1) 설계, 분석
우선순위 큐를 사용하면 쉽게 풀린다.
heap도 복습해 볼 겸 직접 heap을 만들어서 해결했다.
2) 풀이
#include <iostream> #include <vector> using namespace std; class MinHeap { private: std::vector<int> heap; void goUp(int index) { while (index > 0) { int parent = (index - 1) / 2; if (heap[index] < heap[parent]) { std::swap(heap[index], heap[parent]); index = parent; } else break; } } void goDown(int index) { int size = heap.size(); while (true) { int left = 2 * index + 1; int right = 2 * index + 2; int smallest = index; if (left < size && heap[left] < heap[smallest]) smallest = left; if (right < size && heap[right] < heap[smallest]) smallest = right; if (smallest != index) { std::swap(heap[index], heap[smallest]); index = smallest; } else break; } } public: void push(int val) { heap.push_back(val); goUp(heap.size() - 1); } void pop() { if (heap.empty()) return; heap[0] = heap.back(); heap.pop_back(); goDown(0); } int top() const { if (!heap.empty()) return heap[0]; throw std::runtime_error("Heap is empty"); } bool empty() const { return heap.empty(); } int size() const { return heap.size(); } }; int main () { ios::sync_with_stdio(false); cin.tie(nullptr); int N; MinHeap minheap; cin >> N; for (int i=0; i<N; i++) { int temp; cin >> temp; if (temp == 0) { if (!minheap.empty()) { cout << minheap.top() << '\n'; minheap.pop(); } else cout << 0 << '\n'; } else { minheap.push(temp); } } }
1. 친구 네트워크(4159)
1) 문제
문제 설명
민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.출력
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <iostream> #include <vector> #include <string> #include <unordered_map> using namespace std; vector<int> parent; vector<int> sizeOfSet; unordered_map<string, int> personToID; int T, F; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } int Union(int A, int B) { A = Find(A); B = Find(B); // 같은 집합이 아니면 합치기 if (A!=B) { parent[B] = A; sizeOfSet[A] += sizeOfSet[B]; } return sizeOfSet[A]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> T; while(T--) { cin >> F; string freindcase; string p1,p2; int answer = 0; int id = 0; personToID.clear(); parent.clear(); sizeOfSet.clear(); parent.resize(2*F); sizeOfSet.resize(2*F); for (int i=0; i<F; i++) { cin >> p1 >> p2; if (personToID[p1] == 0) { personToID[p1] = ++id; // 맨 처음 부모는 자기 자신 parent[id] = id; // 처음 크기는 1 sizeOfSet[id] = 1; } if (personToID[p2] == 0) { personToID[p2] = ++id; // 맨 처음 부모는 자기 자신 parent[id] = id; // 처음 크기는 1 sizeOfSet[id] = 1; } cout << Union(personToID[p1], personToID[p2]) << "\n"; } } return 0; }
