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번 연산을 할지 선택할 수 있기 때문이다. 처음에는 단순히, 덱의 사이즈를 반으로 나눠 구하고자 ..

이어서 2편을 시작하겠다. 링크는 www.youtube.com/watch?v=La_SITByzxQ&t=134s 이다. 3:00부터의 과정을 진행하려고 한다. 지난 1편에서 이렇게 창문을 완성 시켰다. 하지만 저기 있는 것은 창문 뿐만이 아니다. H키로 벽면을 숨겨뒀었다. 그래서 지금은 보이지 않지만, 창문 주변으로 벽면이 있다는 것을 인지 해야한다. 일단 A키를 누르면 보이는 창문 전체가 노랗게 선택이 된다. G(이동)키를 누르고, Y키(Y축)를 눌러 앞으로 조금 빼준다. 주변의 벽과 분리시켜 보기 위함이다. 그리고 Alt+H를 눌러보면 다음과 같은 화면을 볼 수 있다. 창문을 주변 벽보다 조금 더 안쪽으로 넣어줄 것이다. 하지만 지금은 벽면도 다 같이 선택이 되어 있어서, 창문만을 선택을 해야한다. 일..

백준 단계별 풀기에서 큐,덱 다섯번째 문제이다. 링크는 아래와 같다. 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..