큐(queue)7 [Baekjoon] 1021번: 회전하는 큐 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 문제 해결 과정 착안 양방향에서 요소를 삽입(enqueue) 및 제거(dequeue) 할 수 있는 큐 자료 구조인 덱(deque) 자료 구조를 활용하는 것을 유도한 문제인 것 같은데, 다음과 같은 원리에 의해 한 방향으로만 요소를 삽입/제거하는 큐(queue) 자료 구조를 이용해도 문제를 해결할 수 있다. 덱의 크기를 $N$, 특정 요소를 맨 앞으로 보내기 위한 2번 연산의 실행 횟수를 $k_.. 2023. 6. 25. [Baekjoon] 1966번: 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 해결 과정 착안 얼핏 보았을 때 우선순위 큐와 같은 동작인 것처럼 보이나, 현재 문서의 우선순위보다 우선순위가 높은 문서가 큐에 하나라도 있는 경우 현재 문서를 큐의 가장 뒤쪽으로 보내는 작업 때문에 std::priority_queue 클래스를 사용해봤자 해결에 별 도움이 되지 않을 것이라 판단하였다. 본래 큐 클래스는 Front의 값에 대해서만 확인 가능하고 큐의 중간에 있는 요소들은 접근할 .. 2023. 6. 17. [Baekjoon] 11866번: 요세푸스 문제 0 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 해결 과정 착안 입력받은 $N$ 과 $K$ 의 값에 따라 큐(queue) 자료 구조를 사용해 요소를 하나씩 dequeue하고 반복문의 현재 루프가 $K$ 의 배수 번째에 해당하는 루프이면 숫자를 출력, 아니라면 다시 enqueue를 수행하여 문제를 해결하고자 했다. 구현 크기가 고정된 큐 자료 구조를 사용하며, enqueue 및 dequeue 연산을 반복적으로 수행하기 때문에 효율적인 메모리 활용을 위하여, 문제에 맞게 원형 큐(circular queue, 환형 큐) 자료 구.. 2023. 6. 14. [자료 구조] 선형(Linear) 자료 구조 (2) 스택(Stack), 큐(Queue) 포스트를 읽으실 때 참고하실 점 해당 카테고리의 포스트들은 C/C++ 언어를 기준으로 작성되어 다른 언어에는 적용되지 않는 내용이 일부 포함될 수 있습니다. 또한, 글의 배치나 띄어쓰기는 PC 버전 전체 화면 크기를 기준으로 작성됩니다. 틀린 부분이 있는 경우, 댓글이나 이메일로 연락주시면 내용을 정정하도록 하겠습니다. 지난 포스트에서 배열, 연결 리스트에 대한 키워드를 정리(정리한 거 맞나?...)해봤는데 이번 포스트에서는 나머지 선형 자료 구조인 스택(stack)과 큐(queue), 그리고 자료 구조를 공부할 때 지속적으로 접하게 되는 개념인 추상 자료형(abstract data type, ADT)의 개념에 대해 정리해보려고 한다. 스택(Stack) 스택은 기본적으로 나중에 들어온 자료를 먼저 내보내.. 2023. 5. 9. [Baekjoon] 1260번: DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어지는 간선 정보를 바탕으로 깊이 우선 탐색(depth-first search, DFS)과 너비 우선 탐색(breadth-first search, BFS) 알고리즘을 구현하는 것을 요구하는 문제이므로, 두 알고리즘의 특징에 유의하여 구현하고자 하였다. 깊이 우선 탐색 알고리즘은 스택(stack) 자료 구조를 활용하여 구현(또는 .. 2023. 5. 8. [Baekjoon] 24444번: 알고리즘 수업 - 너비 우선 탐색 1 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 문제 해결 과정 착안 간선(edge)의 가중치가 모두 일정한 무향(undirected) 그래프(graph) 자료 구조에서의 너비 우선 탐색 알고리즘(breadth-first search, BFS)을 구현하는 문제이므로, 간단한 그래프 클래스와 문제에서 요구하는 너비 우선 탐색 알고리즘을 구현하였다. 이번에도 한 정점에 대한.. 2023. 5. 7. 이전 1 2 다음
