원형 큐 (Circular Queue) 앞서 선형 큐의 단점을 설명하면서 rear가 가리키는 인덱스에 삽입한다고 했습니다. 이는 큐의 크기에 따라 제한될 수 있다고 했습니다. 원형 큐는 이 점을 개선할 수 있습니다. 어떤 방식으로 개선할 수 있을까요? 큐의 삽입 함수인 enqueue()에서는 rear을 1 증가시키면서 다음 인덱스에 큐를 삽입할 수 있습니다. 만약 MAX_QUEUE_SIZE에 인덱스가 접근하려고 하면 자동으로 인덱스를 0으로 만들어주면 될 것입니다. 이렇게 숫자가 꽉 차면 0으로 돌아가는 현상을 어디서 겪을 수 있을까요? 바로 나머지 연산에서 찾을 수 있습니다. 0을 5로 나누었다고 해봅시다. 수학적으로는 말이 안되지만, 일단 해봅시다. 나머지 연산에 따르면 나머지가 0이 나옵니다. 1를..

큐란? Queue라는 것은 뭘까요? 사전적 의미부터 살펴봅시다. 큐는 줄을 서서 기다리다 라는 의미를 가지고 있습니다. 사람이 줄을 서서 기다리는 모습을 상상할 수 있겠네요. 컴퓨터에서는 데이터가 줄을 이루는 자료 구조라고 생각하면 될 것 같습니다. 우리가 맛집을 찾아갔다고 상상해봅시다. 이 가게는 밥 먹을 시간이 되면 항상 사람이 붐비어 대기줄을 이룹니다. 오늘은 늦게 도착해서 앞에 대기줄이 길게 이루어져있네요. 밥을 먹기 위해 가게에 들어가려면 이 상황에서 어떻게 해야할까요? 앞에 있는 사람이 모두 들어가야 내가 들어갈 수 있겠죠. 그래야 비로소 제 차례가 와 맛집에 들어가 식사를 할 수 있을겁니다. 큐도 마찬가지입니다. 특정 데이터를 꺼내기 위해서는 앞에 있는 데이터를 모두 꺼내야 합니다. 이러한 ..

Problem https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net Comment 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어집니다. 이제 순서대로 K번째 사람을 제거합니다(프로그램에서는 pop 한 다음 다시 push를 하지 않으면 됩니다.). N명의 사람이 모두 제거될 때까지 계속되기 때문에 모든 원소가 pop 될 때까지 반복하면 됩니다. Code Result

Problem https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net Comment 상근이가 개발한 프린터에서 돌고 있는 특정 문서의 프린터물 출력 순서를 구하는 문제입니다. 상근이가 개발한 프린터가 동작하는 알고리즘은 다음과 같습니다. 1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다..

Problem https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net Comment 1번부터 N번 까지의 숫자가 연속적으로 큐에 들어옵니다. 어느 수가 들어와도 큐는 특정 알고리즘에 의해 돌아가게 되는데, 이는 아래와 같습니다. 1. 제일 앞에 있는 숫자는 우선 빠진다(pop). 2. 그 다음 앞에 있는 숫자는 뒤로 간다(pop + push). 자료구조 중 큐를 이용하여 문제를 해결하면 됩니다. 예제 1을 천천히 따라가보겠습니다. 초기 단계 큐 내부:..