Development Artist

백준 단계별 풀기에서 큐,덱 일곱번째, 마지막 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 1. 4가지를 입력 받는다, Testcase 개수를 우선적으로 받고, 각 Testcase 마다 RD연산 함수, 배열의 개수, 배열 3가지를 받는다. 일단은 배열을 어떤 타입으로 받을 것인지에 대한 고민이 필요하다. [x, y, z, q] 이런식으로 입력을 받아야 한다. 필자는 string으로 받아서 parsing을 통해 정수 배열로 만들어 줄 것이다. 일단 string으로 받게 되면 어떤식..

백준 단계별 풀기에서 큐,덱 여섯번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 1. deque를 활용한 문제이다. deque를 활용하면, 회전하는 큐를 구현할 수 있다. 2. 2번, 3번 연산을 하는 최소값을 구하려면, 우선 덱(deque)에서 빼내고자 하는 정수의 위치를 알 수 있어야한다. 그래야 2번 연산을 할지, 3번 연산을 할지 선택할 수 있기 때문이다. 처음에는 단순히, 덱의 사이즈를 반으로 나눠 구하고자 ..

백준 단계별 풀기에서 큐,덱 다섯번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/10866 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 1. Deque 라이브러리를 사용한다. 기본적으로 deque 라이브러리에서 제공하는 함수들이 지금 문제의 전부를 해결할 수 있다. en.cppreference.com/w/cpp/container/deque 해당 링크는 deque 라이브러리를 정리한 곳이다. #include #include using namespace ..

백준 단계별 풀기에서 큐,덱 네 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/1966 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 1. priority queue를 사용한다. 일반 queue와 다른 점은 숫자를 push 할 때 자동으로 정렬을 해준다는 점이다. 1 2 3 4 순서대로 넣는다면, 4 3 2 1로 위치하게 된다. priority_queue.top()을 해보면 4가 먼저 나오는 것을 확인할 수 있다. 2. queue에 값을 넣을 때 pa..

백준 단계별 풀기에서 큐,덱 세 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 1. 원을 이룬다는 것은 Circular Queue를 생각하면 된다. 논리상 구조는 실질적으로 인덱스 0과 7이 붙어 있지는 않지만 붙어있는 것처럼 간주하겠다는 것이다. 2. 요세푸스 문제를 예로, N=3 이라면 3, 6, 9, 12 의 순서대로 정수값들을 뺀다. 그렇다면, queue의 front값을 읽어 해당 순서를 제외하고는 다시 queue에 넣어주면 된다. 3 6 9 번째 숫자들은 출력을 해주고 pop을 통해 빼준다. 이..

백준 단계별 풀기에서 큐,덱 두 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 1. for문으로 i=1부터 해서 N까지 숫자들을 queue에 push한다. 2. 하나가 남을때 까지 = queue의 사이즈가 1이 될 때 까지. 따라서 while문으로 하고 조건은 queue.size() > 1로 한다. #include #include using namespace std; int main() { ios_base::sync_w..

백준 단계별 풀기에서 큐,덱 첫 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 1. 큐의 구조는 위의 그림과 같다. 선입선출, 즉, 먼저 들어간 데이터가 먼저 나오는 방식으로, 스택의 선입후출과는 다른 개념이다. 스택에서는 아랫 부분이 막혀있었다면, 큐의 경우는 고속도로의 터널을 생각하면 될 듯하다. 흔히들, 사람들의 줄서기의 예시를 많이 든다. 먼저 와서 줄을 기다린 사람이 먼저 기다림을 해소..