JUNOTE

큐란 선입선출(FIFO) 구조를 갖는 자료구조이다. 큐에 대한 자세한 설명은 전 포스팅을 참고하기 바란다.2024.06.15 - [CS/자료구조] - [자료구조] 큐 (Queue) [자료구조] 큐 (Queue)큐란?큐는 스택과 마찬가지로 컴퓨터에 있어서 중요한 자료구조 중 하나이다.큐는 후입선출(LIFO)인 스택과 달리 선입선출(First-In First-Out: FIFO) 구조를 갖는 자료구조이다. 스택에서는 접시 더미junote.tistory.com 큐 구현 방법큐를 구현하는 것은 크게 두 가지 방법이 있다.배열(Array) 기반 큐: 고정 크기의 배열을 사용하여 큐를 구현한다. 간단하지만 큐의 크기가 고정되어 있다는 단점이 있는 방법이다.연결 리스트(Linked-List) 기반 큐: 동적으로 크기를..

큐란?큐는 스택과 마찬가지로 컴퓨터에 있어서 중요한 자료구조 중 하나이다.큐는 후입선출(LIFO)인 스택과 달리 선입선출(First-In First-Out: FIFO) 구조를 갖는 자료구조이다. 스택에서는 접시 더미를 예로 들었다면 큐에서는 음식점 대기줄을 예로 들 수 있다. 음식점의 대기줄에서는 먼저 온 사람이 먼저 식당에 들어갈 수 있다.큐는 선입선출 구조이므로 먼저 들어온 데이터가 먼저 나간다. 큐의 연산큐의 주요 연산은 다음과 같다.Enqueue(): 큐의 끝에 새로운 요소를 추가(삽입)Dequeue(): 큐의 앞에서 요소를 제거(제거)front(): 큐의 맨 앞에 있는 요소를 제거하지 않고 반환rear(): 큐의 맨 뒤에 있는 요소를 제거하지 않고 반환 큐의 구현과 예시 (JAVA)큐를 구현하는..

백준 24511번: queuestack https://www.acmicpc.net/problem/24511 24511번: queuestack 첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄 www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 일단 문제가 길고 복잡해 보인다. 하지만 이 문제의 핵심을 알면 어렵지 않게 문제를 해결할 수 있다. 핵심은 바로 스택일 경우 원래 저장되어 있는 원소는 그 스택 안에만 있고 문제 풀이에는 아무 영향이 없다는 것이다. 스택은 후입선출 구조..

백준 11866번: 요세푸스 문제 0 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 요세푸스 순열을 구하는 문제이다. 일반화 된 요세푸스 순열을 구하는 방법은 두 자연수 n, k가 주어졌을 때, 1부터 n까지의 자연수를 원형으로 배치한 후, 1부터 시작하여 k번째 수를 제거는 것을 숫자가 한 개 남을 때까지 반복했을 때, 마지막 남는 수를 구하면 된다. 이 문제에서는 수를 버리는 순열을 구하는 것이다. 이는 큐를 이용해 구현할 수 있다. 원형 큐를 떠올리시는 분들이 많을 것 같은데 굳이 ..

백준 2164번: 카드 2 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 1부터 n까지의 숫자가 오름차순으로 놓여 있고 처음 숫자를 버리고 다음 숫자를 맨 뒤로 옮기고 그 다음 숫자를 버리는 과정을 반복한 후, 제일 마지막에 남는 숫자를 구하는 문제이다. 큐를 이용하면 간단하게 문제를 해결할 수 있다. 큐에 대한 내용은 전 포스팅을 참고하시기 바란다. 참고 2024.02.07 - [백준 baekjoon]..

백준 18258번: 큐 2 https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 큐를 구현한 다음, 주어진 명령어를 처리하는 문제이다. STL queue를 이용하면 쉽게 풀 수 있다. 큐를 구현하기 위해서는 배열을 이용하는 것이 일반적이다. 큐를 구현하는 것이 이 문제가 원하는 것이겠지만 큐를 구현하는 것은 나중에 따로 포스팅을 해 보도록 하겠다. STL을 이용하면 문제에서 요구하는 명..

백준 12789번: 도키도키 간식드리미 https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 문제가 길어서 어렵게 느껴질 수 있지만 문제의 핵심 부분만 놓고 보면 그렇게 어렵지 않은 문제이다. 줄을 서고 있는 학생의 수가 주어지고 이어서 그 학생들의 번호표 숫자가 서 있는 순서대로(=> 큐와 같은 구조) 주어진다. 옆으로 빠질 수 있는 공간은 사람이 한 명밖에 지나가지 못하고(=> 스택과 같은 구조) 따라서 ..