프로그래밍 공부 노트

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 회의실을 최소로 사용하는 방법은 어느 시각에 동시에 진행되는 회의의 수의 최댓값과 같다. 따라서 라인스위핑을 이용해 동시에 진행되는 회의의 개수를 센 뒤, 이 때의 최댓값을 계산해 출력한다. #include #include using namespace std; typedef pair pii; #define _crd first #define _stat second #define MAX_N 100..

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 회의실을 최소로 사용하는 방법은 어느 시각에 동시에 진행되는 회의의 수의 최댓값과 같다. 따라서 라인스위핑을 이용해 동시에 진행되는 회의의 개수를 센 뒤, 이 때의 최댓값을 계산해 출력한다. #include #include using namespace std; typedef pair pii; #define _crd first #define _stat second #define MAX_N 100..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 점수는 곧 각 카드에 쓰인 수의 합이므로, 카드에 쓰인 수의 합을 최소화하려면 카드를 골라 더할 때 항상 그 값이 가장 작은 두 카드를 골라야 한다. 따라서 이 문제는 우선순위 큐를 이용해 모든 연산을 마친 뒤 각 성분의 합을 구하는 문제이다. #include #include using namespace std; typedef unsigned long long..

https://www.acmicpc.net/problem/17225 17225번: 세훈이의 선물가게 첫 줄에 상민이가 선물 하나를 포장하는 데 걸리는 시간 A, 지수가 선물 하나를 포장하는 데 걸리는 시간 B, 어제 세훈이 가게의 손님 수 N(1 ≤ N ≤ 1,000)이 주어진다. 이후 N개의 줄에 걸쳐 1번부 www.acmicpc.net 각 주문을 주문이 들어온 시간 t와 선물의 개수 m을 지닌 구조체로 저장한다고 하자. 입력으로 주어지는 주문들을 포장지 별로 분류하여 시간의 오름차순으로 저장한 뒤, 두 포장지의 주문이 들어온 순서대로 포장한다. 포장이 다 끝나고 난 뒤엔 포장한 주문의 t에 포장하는 시간을 더한 뒤 m을 1 빼고, m이 0이 되면 다음 주문에 대해 같은 작업을 수행하면 충분히 빠른 시..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 기본적으로는 최소 힙을 사용하되, int형 값을 절댓값과 부호로 나누어 저장하는 클래스에 담은 뒤, 클래스의 비교 함수를 새로 작성해 사용한다. #include #include #include using namespace std; #define MAX_N 100000 // int를 절댓값과 부호로 나누어 저장 class num { public: // 실제 값이 음수라면 tru..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 최대 힙을 구현하는 문제이다. STL을 사용해 풀 수도 있고, 아니면 힙을 직접 구현해 풀 수도 있다. - STL #include #include using namespace std; int main() { // 입출력 속도 향상 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // N: 연산의 개수, x: 각 연산 i..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 항상 정렬되어 있는 배열에서 push와 최대/최솟값의 pop이 여러 번 이루어져야 하므로, 주어진 문제는 수를 두 개의 힙 혹은 하나의 이진 탐색 트리에 저장해 각 연산을 수행하여 문제를 풀 수 있다. - 힙 C++에서 우선순위 큐는 힙으로 구현되어 있으므로, 최대 우선순위 큐와 최소 우선순위 큐를 각각 선언해 힙으로 사용한다. 이 때 최대 힙에서 pop한 원소는 최소 힙에 그대로 남아있고, ..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 최소 힙을 구현하는 문제이다. C++에선 priority_queue라는 힙 구조가 STL로 존재하지만, 분할 상환 기법을 사용하기 때문에 직접 구현하는 것보다 메모리를 많이 소모한다 - 직접 구현 #include using namespace std; #define MAX 100000 int heap[MAX + 1] = { 0, }; // 힙의 두 인덱스를 받아 값을 swap하고..