컴퓨터하는 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..

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

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 해결 알고리즘 보드에 뱀의 위치를 1로 표시해 주고 뱀의 머리부분부터 꼬리 부분까지는 순서대로 전부 큐에 넣고 게임이 언제 끝나는지 그 시간을 출력해주면 된다. (큐를 이용하는 게 이 문제의 핵심인 것 같다.) 소스 코드 #include using namespace std; int N; int board[102][102]; queue q; // 방향 전환 queue snake; // 뱀의 길이 및 ..

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..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제보다 입력 출력이 더 중요하다. 문제 해결 알고리즘 맵을 사용해서 키값을 각각 문자열과 숫자에 부여한 맵을 두개 만들어서 입력에 포켓몬 이름이 나오든 숫자가 나오든 바로 출력 할 수 있게 한다. 소스 코드 #include using namespace std; int main(){ cin.tie(0); ios_base::sync_with_stdio(false); in..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 해결 알고리즘 스택 수열에 맞게 출력해주는데 이 때, 스택의 맨 위에 있는 수가 주어진 수보다 크면 스택 수열이 될 수 없으므로 그것만 잘 판별해주자 소스 코드 #include using namespace std; int main(){ int cur_num = 1; int n; cin >> n; stack s;..

www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 해결 알고리즘 1. 큐(q)에 1부터 N까지의 숫자들을 순서대로 push해준다. 2. 큐(q)안에 숫자들이 모두 없어질 때까지 K번 옆으로 갈 때 과정에서 지나치는 숫자들은 큐의 맨 앞에서 맨 뒤로 보내고, K번 가서 도착한 그 숫자는 출력하고 큐(q)에서 pop한다. 여기서 큐의 사이즈가 1이 아니면 뒤에 쉼표(,)를 출력한 후 pop한다. 소스 코드 #include using namespace std; int main(){ int N, K; cin >> N >> K; queue q; cout