프로그래밍 공부 노트

https://www.acmicpc.net/problem/17225 17225번: 세훈이의 선물가게 첫 줄에 상민이가 선물 하나를 포장하는 데 걸리는 시간 A, 지수가 선물 하나를 포장하는 데 걸리는 시간 B, 어제 세훈이 가게의 손님 수 N(1 ≤ N ≤ 1,000)이 주어진다. 이후 N개의 줄에 걸쳐 1번부 www.acmicpc.net 각 주문을 주문이 들어온 시간 t와 선물의 개수 m을 지닌 구조체로 저장한다고 하자. 입력으로 주어지는 주문들을 포장지 별로 분류하여 시간의 오름차순으로 저장한 뒤, 두 포장지의 주문이 들어온 순서대로 포장한다. 포장이 다 끝나고 난 뒤엔 포장한 주문의 t에 포장하는 시간을 더한 뒤 m을 1 빼고, m이 0이 되면 다음 주문에 대해 같은 작업을 수행하면 충분히 빠른 시..

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 배열 혹은 벡터를 사용할 경우 인덱스 계산이 힘들지만, 큐를 사용할 경우 push와 pop을 이용해 간단하게 순열을 구할 수 있다. #include #include using namespace std; int main() { // N: 수열의 길이, K: 점프 거리 int N, K, idx = 0; // 순열을 저장할 큐 queue q; // 문제의 조건을 입력받은 뒤 수열의 각 성분을 설정 scanf("%d %d", &N, &K); for (int i = 1; i

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 큐를 구현한 뒤 입력받는 명령에 따라 큐의 각 연산을 실행한다. #include #include using namespace std; #define MAX_N 10000 int main() { // 입출력 속도 향상 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // N: 명령의 수, que: 큐, l, r: 큐의 시작과..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 뱀의 각 좌표를 deque에 push한 뒤, 뱀의 머리가 향할 곳의 좌표를 c라고 하자. c가 위치한 곳이 벽 혹은 뱀의 몸통이므로 게임을 끝내고, 빈 칸 혹은 사과라면 deque의 front에 c를 push한다. 이 때 c가 위치한 곳이 빈 칸이라면 deque의 back을 pop해야 한다. 이 과정을 뱀이 길이 1이고 (1, 1)에서 시작할 때부터 게임이 끝날 때까지 반복하면 문제를 해결할 수 있다. ..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 큐를 덱으로 사용하면, 카드를 제거하는 것은 큐의 원소를 pop하는 것, 카드를 옮기는 것은 큐의 front를 큐에 push한 뒤 다시 큐의 원소를 pop하는 것으로 볼 수 있다. #include #include using namespace std; int main() { // 덱의 초기 카드 수 int N; // 덱 queue q; // 덱의 크기를 입력받은 뒤 q에 덱의 각 카드를 push s..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문서를 {중요도, 출력 순서를 알고싶은 문서인지 여부} 꼴의 pair로 나타내고, 각 문서를 순서대로 큐에 저장한 뒤 문제 조건에 맞게 큐를 순회하며 문서를 큐에서 제거한다. 제거할 문서가 순서를 알고 싶은 문서일 때, 전체 문서의 수에서 큐 안의 문서 수를 출력하면 정답이 된다. #include #include using namespace std; typedef pair doc; #define _p..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 큐를 이용해서 K - 1번 push와 pop을 반복해도 좋지만, K번째 원소를 바로 찾을 수 있는 배열을 이용하는 것이 더욱 빠른 문제이다. #include #include using namespace std; int main() { // N: 순열의 길이, K: 순열의 점프 크기 int N, K, idx = 0; vector v; // 문제의 조건을 입력받은 뒤 순열을 오름차순으로 채운다 scanf("%d %d", &N, &K); for (int i = 0; i < N; i++) v.p..