알고리즘/자료 구조8 백준 9375번 : 패션왕 신해빈 문제 링크 : www.acmicpc.net/problem/9375 내 풀이(2021.1.22.) : #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T; cin >> T; for (int i = 0; i > n; for (int i = 0; i > temp >> temp2; if (m.find(temp2) == m.end()) m[temp2] = 1; else m[temp2] = m[temp2] + 1; //cout 2021. 1. 22. 백준 1620번 : 나는야 포켓몬 마스터 이다솜 문제 링크 : www.acmicpc.net/problem/1620 내 풀이(2021.1.21.) : #include #include #include #include using namespace std; string unsorted[100000]; vector sorted[26]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N >> M; for (int i = 0; i > unsorted[i]; sorted[unsorted[i][0]-'A'].push_back(make_pair(unsorted[i],i)); } for (int i = 0; i < M;.. 2021. 1. 21. 백준 15903번 : 카드 합체 놀이 문제 링크 : www.acmicpc.net/problem/15903 내 풀이(2021.1.4.) : #include #include using namespace std; priority_queue pq; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; for (int i = 0; i > temp; pq.push(temp); } for (int i = 0; i < m; i++) { long long temp1 = pq.top(); pq.pop(); long long temp2 = pq.top(); pq.pop(); pq.push(temp1 +.. 2021. 1. 5. 우선순위 큐와 힙 개념 및 C++ STL 개념 출처 : chanhuiseok.github.io/posts/ds-4/ STL 출처 : chanhuiseok.github.io/posts/algo-54/ * 우선순위 큐 - 우선순위가 높은 순서대로 pop하는 큐 - 우선순위 큐는 배열이나 연결리스트로 구현하는 것보다 힙으로 구현하는 것이 삽입 속도가 더 빠르므로, 힙으로 많이 구현함 * 복잡도 비교 1) 삽입 - 배열/연결리스트 : O(n) - 힙 : O(log2n) 2) 삭제 - 배열/연결리스트 : O(1) - 힙 : O(log2n) * 삽입 방법 1. 새로운 노드를 완전 이진 트리 구조를 유지할 수 있는 위치에 추가한다. 2. 새로운 노드로부터 시작해서, 부모/자식 노드 간에 비교를 통해 swap을 반복한다. * 삭제 방법 1. 루트 노드를 삭제.. 2021. 1. 4. 이전 1 2 다음