덱 (연결리스트로 구현)

덱의 기본 설명은 '덱 (구조체로 구현)'에서 설명을 했으므로 생략하겠다. 백준 10866번 문제를 베이스로 구현한 코드다. 코드 자체는 이중 연결리스트와 유사하다. 또한, 연결리스트로 구현했으므로 full() 함수는 없다. 덱 직접 입력 코드 구현 #include #include typedef struct Node { int data; struct Node *left; struct Node *right; }Node; typedef struct Deque { Node *front; Node *rear; int size; }Deque; void init_deque(Deque *deque) { deque->front = NULL; deque->rear = NULL; deque->size = 0; } int ..

덱 (구조체로 구현)

덱 기본 설명 덱은 간단하게 생각해서 원형 큐를 조금 확장시킨 개념이라 생각할 수 있다. 원형 큐는 rear에서 enqueue를 하고 front에서 dequeue를 했지만, 덱은 여기서 확장해서 front과 rear 모두에서 enqueue와 dequeue를 한다고 생각하면 된다. 코드의 구현에 있어서 생각해야 할 것은, 원형 큐에서의 enqueue를 push_front와 push_back로 나누고, dequeue를 pop_front와 pop_back으로 나누고 코드를 잘 짜야한다는 것이다. 밑에서 설명할 함수들에 있는 full()함수와 empty()함수는 완성된 코드에 있다. void enqueue(Queue* q, int data) { if (full(q)) { printf("큐가 포화상태입니다. 데이..

10866: 덱

10866번: 덱(BOJ C/C++) 사용 언어: C 문제 정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여덟 가지이다. push_front X: 정수 X를 덱의 앞에 넣는다. push_back X: 정수 X를 덱의 뒤에 넣는다. pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 덱에 들어있는 정수의 개수를 출력한다. empty: 덱이 비어있으면 1을, 아니면 0을 출력한다. front: 덱의 가장 앞에 있는 정..

1158: 요세푸스 문제

2493번: 탑(BOJ C/C++) 사용 언어: C 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 첫 번째 풀..

18258: 큐 2

18258번: 큐 2(BOJ C/C++) 사용 언어: C 문제 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의..

2839: 설탕 배달

2839번: 설탕 배달(BOJ C/C++) 사용 언어: C 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 출력..

1966: 프린터 큐(BOJ C/C++)

1966번: 프린터 큐(BOJ C/C++) 사용 언어: C 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Qu..

큐 (연결리스트로 구현)

연결리스트로 큐를 구현하므로 크기에 제약이 없어 큐가 꽉 찼는지 검사할 필요가 없으므로 full() 함수가 필요가 없다. 큐의 기본적인 설명은 '선형 큐 (구조체로 구현)'에서 설명했으므로 생략하겠다. 원형 큐는 선형 큐를 보완한 형태지만, 여전히 배열 때문에 크기에 제약을 받는 단점을 보인다. 연결리스트로 구현한 큐는 이러한 단점을 없애서 큐를 구현할 수 있는 가장 효율적인 방법이라고 볼 수 있다. 구현 #include #include #include typedef struct Node //노드 정의 { int data; struct Node *next; }Node; typedef struct Queue //Queue 구조체 정의 { Node *front; //맨 앞(꺼낼 위치) Node *rear; ..