우선순위 큐6 [Baekjoon] 18405번: 경쟁적 전염 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 해결 과정 착안 우선순위 큐(priority queue) 자료 구조를 활용하여, 바이러스 번호가 낮은 순으로 먼저 너비 우선 탐색(breadth-first search, BFS)을 수행함으로써 문제를 해결하고자 하였다. * 우선순위 큐 대신, 배열 및 정렬 알고리즘을 사용하여 해결하면 속도 측면에서 더 유리한 것 같다. 구현 좌표를 나타내기 위한 구조체 Coor.. 2023. 7. 21. [Baekjoon] 11399번: ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 해결 과정 착안 뒤에서 기다리는 사람이 돈을 인출하려면 자신보다 앞 번호에 대기 중인 사람들이 모두 돈을 인출해야하므로, 각 사람이 돈을 인출하는데 필요한 시간의 총합을 최소로 하기 위해서는 인출하는 시간이 짧은 사람을 앞에 배치하여야 한다. 따라서, 우선순위 큐(priority queue) 자료 구조를 이용하여 인출하는 시간의 정보를 저장한 다음, 최소 인출시간인 사람부터 순차적으로 우선순위 큐에서 추출하는 방식을 활용.. 2023. 7. 13. [Baekjoon] 1966번: 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 해결 과정 착안 얼핏 보았을 때 우선순위 큐와 같은 동작인 것처럼 보이나, 현재 문서의 우선순위보다 우선순위가 높은 문서가 큐에 하나라도 있는 경우 현재 문서를 큐의 가장 뒤쪽으로 보내는 작업 때문에 std::priority_queue 클래스를 사용해봤자 해결에 별 도움이 되지 않을 것이라 판단하였다. 본래 큐 클래스는 Front의 값에 대해서만 확인 가능하고 큐의 중간에 있는 요소들은 접근할 .. 2023. 6. 17. [Baekjoon] 1197번: 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 해결 과정 착안 최소 (비용) 신장 트리(minimum spanning tree, MST)를 구하는 문제이므로, 이를 구하는 대표적인 알고리즘을 이용하여 문제를 해결하고자 하였다. 문제에서 한 줄씩 간선 데이터를 입력으로 제공하기 때문에, 간선 데이터를 하나씩 저장하면서 정렬하는 것이 문제 해결에 편리할 것 같아서 크루스칼 알고리즘(Kruskal.. 2023. 5. 31. [Baekjoon] 16236번: 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 해결 과정 착안 문제에서 아기 상어가 물고기를 먹기 위해 이동하는 최소 경로가 크기에 따라 달라지는 상황에서, 아기 상어가 먹이를 찾아 탐색하는 과정을 구현하는 문제이다. 문제를 처음 접했을 때, 아기 상어의 1 초당 이동 반경을 중심으로 전방향으로 탐색을 하는 방법을 생각해보았다. 즉, 너비 우선 탐색(breadth-first search, BFS)의 원리에 기반하여 주어진 공간 내.. 2023. 5. 30. [C++ 기초] STL priority_queue 템플릿 클래스 STL priority_queue 템플릿 클래스 std::priority_queue 클래스는 헤더 내에 포함된 컨테이너로, 비선형 자료 구조 중의 하나인 우선순위 큐(priority queue) 역할을 하는 컨테이너이다. 우선순위 큐는 종종 알고리즘 문제를 해결하기 위해 쓰이는데 힙(heap) 트리를 직접 만들어 구현할 수도 있으나, 편의상 매번 해당 자료 구조들을 직접 구현하는 것이 번거로워 STL에서 제공하는 템플릿 클래스 사용법을 정리해놓으려고 한다. // std::priority_queue 클래스의 템플릿 매개변수 template _Ty : 일반화 된 자료형. _Container : 임의 접근.. 2023. 5. 30. 이전 1 다음
