본문 바로가기
study/자료구조

[Chap4] 과제

by 메이02 2023. 3. 28.

[과제 1]  - 백준 18258을 원형 큐로 변형

더보기

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

  • push X: 정수 X를 큐에 넣는 연산이다.
  • pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 큐에 들어있는 정수의 개수를 출력한다.
  • empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
  • front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

#include <iostream>
using namespace std;
#include <string>
const int MAX_QUEUE_SIZE = 8;
class CircularQueue {
private:
	int front;
	int rear;
	int queue[MAX_QUEUE_SIZE] = { 0, };
public:
	CircularQueue() { front = rear = 0; }
	bool isEmpty() { return front == rear; }
	bool isFull() {
		return ((rear + 1) % MAX_QUEUE_SIZE) == front;}
	void push(int);
	int pop();
	void Size();
	void Front();
	void Back();
	void empty();
};
void CircularQueue::push(int num) {
	if (isFull())
	{
		cout << "큐가 포화상태입니다." << endl; exit(-1);
	}
	else
	{
		rear = (rear + 1) % MAX_QUEUE_SIZE;
		queue[rear] = num;
	}
}
int CircularQueue::pop() {
	if (isEmpty())
	{
		cout << -1 << endl;
	}
	else
	{
		front = (front + 1) % MAX_QUEUE_SIZE;
		cout << queue[front] << endl;
		return queue[front];
	}
}
void CircularQueue::Size() {
	if (rear < front) {
		int maxi = rear + MAX_QUEUE_SIZE;
		cout << maxi - front - 1<< endl;
	}
	else {
		cout << rear - front << endl;
	}
}
void CircularQueue::Front() {
	if (!isEmpty()) {
		cout << queue[front+1] << endl;
	}
	else {
		cout << -1 << endl;
	}
}
void CircularQueue::Back() {
	if (!isEmpty()) {
		cout << queue[rear] << endl;
	}
	else {
		cout << -1 << endl;
	}
}


int main()
{
	int N;
	cin >> N;
	CircularQueue q;
	string s;
	int data = 0;
	for (int i = 0; i < N; i++) {
		cin >> s;
		if (s == "push") {
			cin >> data;
			q.push(data);
		}
		else if (s == "pop") {
			q.pop();
		}
		else if (s == "size") {
			q.Size();
		}
		else if (s == "empty") {
			if (q.isEmpty()) {
				cout << 1 << endl;
			}
			else {
				cout << 0 << endl;
			}
		}
		else if (s == "front") {
			q.Front();
		}
		else if (s == "back") {
			q.Back();
		}
		
	}

	return 0;
}

*내가 큐랑 스택에서 잘 모르겠는 부분은, return data[k] 하면은 data배열에서 k인덱스의 요소가 사라지냐는 것이다... 그게 젤 궁금해

[과제 2]

더보기

1번부터 N번까지 

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람과 K+1번째 사람을 제거한다. 두 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 오직 1명의 사람이 남을 때까지 또는 더 이상 제거할 수 없을 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K, 1)-순열이라고 한다. 예를 들어 (7, 3,1)-요세푸스 순열은 <3, 4, 7 , 1 , 6, 2>이다.

N과 K가 주어지면 (N, K, 1)순열을 구하는 프로그램을 작성하시오.

(입력)

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

#include <iostream>
using namespace std;
#include <string>

const int SIZE = 100;
class CircularQueue{
private:
	int front;
	int rear;
	int queue[SIZE];
public:
	CircularQueue() { front = rear = 0; }
	bool isEmpty() { return front == rear; }
	bool isFull() { return ((rear + 1) % SIZE) == front; }
	void push(int);
	int pop();
	int Front();
	int Size();
	int OnlyOne();
	int NoMore();
};

int CircularQueue::OnlyOne() {
	return { (((rear + 1) % SIZE) == front) || (((front + 1) % SIZE) == rear) };
}
int CircularQueue::NoMore() {
	return { (((rear + 1) % SIZE) == front) || (((front + 2) % SIZE) == rear) };
}
void CircularQueue::push(int num) {
	if (isFull()) {
		cout << "error : 큐가 포화 " << endl; exit(-1);
	}
	else {
		rear = (rear + 1) % SIZE;
		queue[rear] = num;
	}
}
int CircularQueue::pop() {
	if (isEmpty()) {
		cout << "error : 큐가 비어있음 " << endl; exit(-1);
	}
	else {
		front = (front + 1) % SIZE;
		return queue[front];
	}
}
int CircularQueue::Front() {
	if (isEmpty()) {
		exit(-1);
	}
	else {
		return queue[(front + 1)%SIZE];
	}
}
int CircularQueue::Size() {
	if (rear < front) {
		int maxi = rear + SIZE;
		return maxi - front - 1;
	}
	else
	{
		return rear - front - 1;
	}
}


int main() {
	int N, K;
	cin >> N >> K;
	cout << endl;
	CircularQueue q;
	for (int i = 1; i <= N; i++) {
		q.push(i);
	}
	while (!(q.NoMore() || q.OnlyOne())) {
		for (int i = 1; i < K; i++) {
			q.push(q.Front());
			q.pop();
		}
		cout << q.Front() << " ";
		q.pop();
		cout << q.Front() << " ";
		q.pop();
	}
	
	return 0;
}

[과제 3] - 백준 12873번 변형

더보기

백준이는 BOJ 알고리즘 캠프 참가자 중 한 명에게 기념품을 주려고 한다. 하지만, 많은 참가자 중에서 어떤 사람을 뽑아서 기념품을 줘야하는지 고민이 되기 시작했다. 따라서, 백준이는 게임을 통해서 기념품을 받을 사람을 정하기로 결정했다.

게임이 시작하기 전에 모든 참가자 N명은 원을 이루어서 앉아있다. 다음, 1부터 N까지 번호가 적혀있는 티셔츠를 시계방향으로 입는다. 이 티셔츠는 게임에 사용되지 않으며, 게임을 쉽게 하기 위해서 입는 티셔츠이다.

게임은 단계로 이루어져 있으며, 첫 단계는 1단계이다. 각 단계가 시작될 때, 백준이는 어떤 참가자의 앞에 서있다. 그 다음, "하나"를 외친다. 그 다음, 시계 방향으로 다음 사람에게 이동하며 "둘"을 외친다. 이 과정은 t단계인 경우에 t^2+1을 외칠 때 까지 진행한다. 예를 들어, 1단계에서는 1까지 외치며, 2단계에서는 5까지, 3단계에서는 10까지 외친다.

각 단계가 끝난 경우에, 백준이가 앞에 서 있는 사람은 게임에서 제외된다. (t단계인 경우에 t^2+1을 외칠 때 앞에 있던 사람) 사람이 제거된 후에는 백준이는 시계 방향으로 다음 사람에게 이동한다. 1단계에서 백준이는 티셔츠 1번을 입고 있는 사람의 앞에 있다. 게임은 원에 한 명이 남을 때 까지 진행되며, 마지막 남은 사람이 기념품을 가져가게 된다.

참가자의 수 N이 주어졌을 때, 어떤 티셔츠를 입고 있는 사람이 기념품을 받는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 BOJ 캠프 참가자의 수 N (1 ≤ N ≤ 5,000)이 주어진다.

출력

첫째 줄에 기념품을 받는 사람이 입고 있는 티셔츠의 번호를 출력한다.

#include <iostream>
using namespace std;
#include <string>

const int SIZE = 100;
class CircularQueue {
private:
	int front;
	int rear;
	int queue[SIZE];
public:
	CircularQueue() { front = rear = 0; }
	bool isEmpty() { return front == rear; }
	bool isFull() { return ((rear + 1) % SIZE) == front; }
	void push(int);
	int pop();
	int Back();
	int Front();
	int Size();
	int OnlyOne();
	int NoMore();
};

int CircularQueue::OnlyOne() {
	return { (((rear + 1) % SIZE) == front) && (((front + 1) % SIZE) == rear) };
}
int CircularQueue::NoMore() {
	return { (((rear + 1) % SIZE) == front) || (((front + 2) % SIZE) == rear) };
}
void CircularQueue::push(int num) {
	if (isFull()) {
		cout << "error : 큐가 포화 " << endl; exit(-1);
	}
	else {
		rear = (rear + 1) % SIZE;
		queue[rear] = num;
	}
}
int CircularQueue::pop() {
	if (isEmpty()) {
		cout << "error : 큐가 비어있음 " << endl; exit(-1);
	}
	else {
		front = (front + 1) % SIZE;
		return queue[front];
	}
}
int CircularQueue::Front() {
	if (isEmpty()) {
		exit(-1);
	}
	else {
		return queue[(front + 1) % SIZE];
	}
}
int CircularQueue::Back() {
	if (isEmpty()) {
		exit(-1);
	}
	else {
		return queue[rear % SIZE];
	}
}
int CircularQueue::Size() {
	if (rear < front) {
		int maxi = rear + SIZE;
		return maxi - front - 1;
	}
	else
	{
		return rear - front - 1;
	}
}

int main() {
	int N;
	cin >> N;
	CircularQueue q;
	for (int i = 1; i <= N; i++) {
		q.push(i);
	}

	if (!q.OnlyOne()) {
		for (int i = 1; i <= N - 1; i++) {
			for (int j = 1; j < i * i + 1; j++) {
				q.push(q.Front());
				q.pop();
			}
			q.pop();
		}
	}

	cout << q.Front();

	return 0;
}

과제 3번은 과제 2번이랑 비슷한거 같아서 수월하다고 생각했는데, 처음에 i < 100했다가 결과가 출력이 안됐는데, 챗지피티에 물어봐서 i <= N-1 했더니 바로 완성되었다.... 뭐지 진짜 암튼 과제 다 완성 !!!!

'study > 자료구조' 카테고리의 다른 글

[스택 코드]  (0) 2023.04.15
[클래스 코드]  (0) 2023.04.15
[Chap5] 연결 리스트 과제  (0) 2023.04.06
[Chap5] 포인터와 연결리스트  (0) 2023.04.05
[Chap4] 큐  (0) 2023.03.28

관련글

티스토리툴바