컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제 해결 알고리즘 최대 힙과 최소 힙으로 각각 최댓값 최솟값을 알아내고, map을 이용해서 남아있는 원소들의 갯수를 저장해준다. 없으면 힙에서 삭제를 해주어야한다. 오버플로우가 나므로 long long 자료형을 써주어야한다. 소스 코드 #include #define ll long long using namespace std; int main(){ ios_base::sync_with_stdio..

https://www.acmicpc.net/problem/1060 1060번: 좋은 수 정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다. A와 B는 양의 정수이고, A < B를 만족한다. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다. 정수 www.acmicpc.net 문제 해결 알고리즘 S에 속한 숫자들을 먼저 우선순위 큐에 넣고 (이 때, 들어오는 S의 원소들은 정렬되지 않았기 때문에 정렬을 꼭 해주어야한다.) 좋은 구간의 개수는 0이긴 하지만 1로 해주어야 나중에 2 1 3 3 같은 반례로부터 자유롭다. 우선순위 큐에 있는 수들은 작은 수가 먼저 나오게 정렬해준다. 그리고 큐에서 나온 수의 1 큰 수와 1 작은 수의 좋은 구간 개수를..

https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 문제 해결 알고리즘 우선순위 큐를 이용하는 문제. 메모리 관리가 빡세다. 그냥 곱한 값들을 전부 우선순위 큐에 집어넣는 방식으로 하면 메모리 초과를 피할 수 없다. 우선순위 큐의 크기가 N보다 크고 최댓값보다 그 값이 크다면 건너뛰고 중복은 받지 않는 식으로 메모리 관리를 해주어야한다. 시행착오가 참 많았던 문제 소스 코드 #include #define ll long l..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상정렬 알고리즘 문제였으나 가능하면 쉬운 문제부터 푼다는 조건이 들어가있는 문제이다. 이 문제는 위상정렬할 때 쓰이는 큐를 우선순위 큐로 오름차순 정렬해주면 풀리는 문제였다. 아래는 링크는 위상정렬 알고리즘에 대해 자세히 설명되어있다. https://kimmessi.tistory.com/207 소스 코드 #include using nam..

다익스트라 알고리즘 (Dijkstra's algorithm) 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘 다익스트라 알고리즘은 음의 간선이 있는 그래프에서는 사용이 불가능하지만 현실 세계에서는 음의 간선이 존재하지 않으므로 현실 세계에서 쓰기에 적합하다. 다익스트라는 그리디로 분류된다. 매상황 가장 비용이 적은 노드를 선택해 임의의 과정을 반복해준다. 동작 과정 1. 출발 노드를 설정해준다. 2. 최단거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다. 4. 해당 노드에서 다른 노드로 가는 최단 거리 테이블을 갱신해준다. 5. 3번과 4번을 반복한다. 알고리즘 사례 위와 같은 그래프가 있다고 하자 출발점은 0이다. 이제부터 0번 노드..

https://www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 문제 해결 알고리즘 우선순위 큐를 이용해서 맨 위의 두 숫자를 곱한 후 두 수는 pop해주고 곱한 수는 다시 우선순위 큐에 넣는 방식으로 진행한다. 이 때, 결과값에 곱해준다. (모듈러 연산은 결과값 곱해줄 때만 해준다) 마지막에 결과값을 출력해준다. 소스 코드 #include #define MOD int(1e9+7) using namespace std; ..

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 해결 알고리즘 우선순위 큐를 이용한다. 이 때 메모리 초과가 날 수 있으므로 N개 이상 큐에 들어가 있으면 맨 앞에 있는 수를 삭제해주면서 진행해준다. 0 소스 코드 #include using namespace std; priority_queue pq; int main(){ ios::sync_with_stdio(false); cin.tie(); cout.tie(); int N; cin >> N; f..