JUNOTE

백준 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 문제 예제 문제해석 및 풀이 이 문제는 일단 문제가 길고 복잡해 보인다. 하지만 이 문제의 핵심을 알면 어렵지 않게 문제를 해결할 수 있다. 핵심은 바로 스택일 경우 원래 저장되어 있는 원소는 그 스택 안에만 있고 문제 풀이에는 아무 영향이 없다는 것이다. 스택은 후입선출 구조..

백준 2346번: 풍선 터뜨리기 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제에는 n개의 풍선이 원형으로 놓여 있고 각 풍선마다 1번 풍선부터 오른쪽으로 오름차순으로 숫자가 주어진다. 그리고 풍선 안에 정수인 숫자가 적혀 있는데 풍선을 터뜨리면 그 숫자만큼 이동하여 다음 풍선을 터뜨린다. 이를 풍선이 없어질 때까지 반복한다. 입력으로는 풍선의 개수와 풍선 안에 적혀있는 정수들이 차례로 주..

백준 28279번: 덱 2 https://www.acmicpc.net/problem/28279 28279번: 덱 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 덱을 구현해 문제에서 주어진 명령들을 처리하는 문제이다. 덱(deque)는 double-ended-queue의 줄임말로 양쪽으로 삽입 및 삭제가 가능한 자료구조이다. 덱은 스택과 큐의 특성을 모두 갖는다. STL에서도 덱을 지원하기 때문에 이를 이용하면 문제를 쉽게 해결할 수 있다. 지금까지 스택과 큐에서는 STL을 이용해서 이러한 종류의 문제를 풀었지만 이번..

백준 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 문제 예제 문제해석 및 풀이 이 문제는 문제가 길어서 어렵게 느껴질 수 있지만 문제의 핵심 부분만 놓고 보면 그렇게 어렵지 않은 문제이다. 줄을 서고 있는 학생의 수가 주어지고 이어서 그 학생들의 번호표 숫자가 서 있는 순서대로(=> 큐와 같은 구조) 주어진다. 옆으로 빠질 수 있는 공간은 사람이 한 명밖에 지나가지 못하고(=> 스택과 같은 구조) 따라서 ..

백준 4949번: 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 저번 문제인 9012번 괄호 문제보다 조금 더 복잡한 문제이다. 소괄호도 있지만 대괄호가 추가되었다. 그리고 문장을 입력받는다. 이 점을 제외하면 9012번과 유사한 문제이다. 9012번에서는 cnt변수를 이용해서 cnt의 숫자를 이용해서 풀었지만 이번에는 stack라이브러리를 이용해서 풀어볼 것이다. 9..

백준 9012번: 괄호 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 첫 줄에 테스트 케이스의 개수 T가 주어지고 T개의 테스트를 진행하고 괄호가 올바르게 쓰였으면 YES를 출력하고 올바르지 않게 쓰였으면 NO를 출력하는 문제이다. 처음에는 (의 개수와 )의 개수가 같기만 하면 되는 줄 알고 코드를 짜보았으나 결과는 '틀렸습니다' 였다. 반례를 생각해보니 입력이 ))(( 로..

백준 10773번: 제로 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 주어지는 정수들을 차례로 입력하다가 0이 입력되면 가장 최근 입력된 정수를 삭제하고 마지막에는 입력된 모든 정수의 합을 출력하는 문제이다. 문제를 보자마자 어떻게 풀어야 할 지 감이 오는 어렵지 않은 문제였다. 벡터를 이용해 입력을 받다가 0이 입력되면 가장 최근에 입력받은 정수를 삭제하는 방식으로 ..