스택이란? Stack이라는게 뭘까요? 사전적 의미부터 살펴봅시다. 스택은 쌓다, 포개다 라는 의미를 가지고 있습니다. 말 그대로 데이터를 쌓아서 자료를 저장하는 구조입니다. 우리가 책을 위로 쌓아서 보관해놓았다고 생각해봅시다. 맨 밑에 있는 책을 꺼내기 위해선 어떻게 해야 할까요? 위에 있는 책들을 다 어딘가로 치운 다음 꺼내야 할 것입니다. 스택도 마찬가지입니다. 특정 데이터를 꺼내기 위해서는 위에 있는 데이터를 다 빼내야 합니다. 그래서 스택은 후입선출(LIFO; Last In First Out)의 특징을 가지고 있습니다. 스택 ADT 스택에 요소를 추가하거나 삭제하는 연산, 현재 스택 상태를 검사하는 연산들로 구성됩니다. create(size) ::= 크기가 size인 스택 생성 is_full(s)..

Problem https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net Comment 괄호가 맞지 않으면 no, 괄호가 맞으면 yes를 출력하는 프로그램입니다. 받은 문자열을 한 문자씩 읽어보면서 여는 괄호( '(' , '[' )는 스택(s)에 넣어 닫는 괄호( ')' , ']' )가 나올 때마다 스택(s)의 제일 위에 있는 값(s.top())과 비교하면 됩니다. Code Result Remark 프로그램에서 값을 받을 때 한 줄씩 받기 ..

Problem https://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 Comment 문제에서 '1부터 N까지의 수를 오름차순으로 차례대로 스택에 push한다'고 명시되어 있습니다. 맨 처음에 정수 N을 받고 반복문을 통해 1부터 차례대로 넣어줍니다. 넣어주는 과정 속에서 둘째 줄부터 N개의 정수를 받을텐데, 매번 넣을 때마다 비교를 해주어야 합니다. 만약 스택에 A라는 ..

Problem https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net Comment 처음에 한 개의 정수(N)를 받습니다. 이는 앞으로 N개의 정수를 받겠다는 것입니다. N개의 정수를 받으면서, 0을 입력받는 경우가 생깁니다(문제에서는 이를 '잘못된 수를 입력받을 때'라고 하는군요.). 이 때, 0을 입력받으면 '최근에 받은 정수 하나를 지웁'니다. (스택이라는 힌트를 여기서 얻어내면 됩니다.) 정수 값을 다 입력받았..

Problem https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net Comment 자료구조 중 스택을 응용한 문제입니다. 문자열을 받아 처음부터 문자 하나하나씩 찾습니다. 만약 '여는 괄호'를 찾는다면 스택에 push 합니다. '닫는 괄호'라면 스택에서 pop합니다. 스택에 뭐가 들어있던 상관 없습니다(단, 무엇인가가 들어있어야 합니다. 그렇지 않으면 그 문자열은 괄호의 짝이 맞지 않다는 뜻입니다.). 모든 문자열의 원..

Problem https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net Comment 자료구조의 스택을 구현하면 됩니다. 문제에서 요구하는 명령의 개수는 5개입니다. push / pop / size / empty / top입니다. 수행해야 하는 명령은 다음과 같습니다. push: 정수를 스택에 넣습니다. pop: 스택에서 가장 위에 있는(스택은 먼저 들어간 원소를 나중에 빼기 때문에 제일 늦게 들어간 원소가 먼저 빠집니다.) 정수를 빼..