Development Artist

백준 단계별 풀기에서 큐,덱 여섯번째 문제이다. 링크는 아래와 같다. 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. 큐의 구조는 위의 그림과 같다. 선입선출, 즉, 먼저 들어간 데이터가 먼저 나오는 방식으로, 스택의 선입후출과는 다른 개념이다. 스택에서는 아랫 부분이 막혀있었다면, 큐의 경우는 고속도로의 터널을 생각하면 될 듯하다. 흔히들, 사람들의 줄서기의 예시를 많이 든다. 먼저 와서 줄을 기다린 사람이 먼저 기다림을 해소..

백준 단계별 풀기에서 스택 6번째 마지막 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net '시간 초과'로 인해서 꾀나 고생한 문제였다. 처음으로, 프로그램의 결과물을 만들어내는 것뿐만 아니라, 효율적인 프로그래밍은 어떤 것인가에 대한 고민을 해보았던 문제였다. 처음 디자인한 것은, N만큼 숫자를 받으면 vector 변수(a)와 stack 변수(b)를 선언하고 각각 push하였다. 또, 결과값을 저장할 vector변수(c)를 선언하였다. a는..

백준 단계별 풀기에서 스택 5번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제를 보고 바로 이해하기 어려웠다. 입출력 예제를 보면서 결과를 따라가본 후에야 어떤 문제인지 알게 되었다. 기존에 풀었던 스택 문제와는 난이도가 있었다. 이전 문제들은 문제를 보고 바로 어떤식으로 풀어야 겠다라는 그림이 바로 그려졌었는데, 이번은 아니였다. 1...

백준 단계별 풀기에서 스택 4번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 이 문제는, 정말 애를 많이 먹은 문제였다. 런타임에러, 출력초과, 틀렸습니다를 엄청 많이 보았기 때문이다. 접근 자체는 어렵지 않았다. 이전의 괄호 문제를 풀어 보았다면, [ ] 괄호가 하나 더 추가 된 것이였다. 그래서 ( [ 일때는 스택에 넣고, ) ] 일때는 스택의 empty 여부와 스택의 top을 확인하여 ( [ 이면 po..

백준 단계별 풀기에서 스택 3번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 이 문제에서는 규칙을 찾는 것이 꾀나 중요할 것이다. 처음으로 생각 했던 것은, '('의 개수와 ')' 개수가 같으면 VPS일 것이다 라고 생각했다. 하지만 ( ) ) ( ( ) 의 경우를 보자. 개수는 3개, 3개로 같으나, 가운데의 ')' 와 '('는 짝을 이루지 못한다. 따라서, 개수가 같은 것이 VPS를 모두..