JUNOTE

스택이란 후입선출(LIFO) 구조를 갖는 자료구조이다. 스택에 대한 자세한 설명은 전 포스팅을 참고하기 바란다.2024.06.15 - [CS/자료구조] - [자료구조] 스택 (Stack) [자료구조] 스택 (Stack)스택이란?스택은 컴퓨터에서 매우 자주 사용되는 자료구조이기 때문에 굉장히 중요한 자료구조이다.Stack이라는 단어를 단어사전에 검색하면 "무더기(더미)"라는 결과를 얻을 수 있다. 스택은 말junote.tistory.com 스택 구현 방법스택을 구현하는 방법에는 크게 2가지 방법이 있다.배열(Array) 기반 스택: 고정 크기의 배열을 사용하여 스택을 구현한다. 배열의 크기를 초과하면 새로운 배열을 할당해야 한다.연결 리스트(Linked-List) 기반 스택: 동적 크기의 연결 리스트를 사..

스택이란?스택은 컴퓨터에서 매우 자주 사용되는 자료구조이기 때문에 굉장히 중요한 자료구조이다.Stack이라는 단어를 단어사전에 검색하면 "무더기(더미)"라는 결과를 얻을 수 있다. 스택은 말 그대로 쌓아놓은 무더기라고 할 수 있다. 식당에서 접시를 쌓아두고 사용하는 것을 상상해보자. 그릇을 사용하려면 맨 위에 있는 그릇을 들어야 한다. 그리고 그릇을 더 추가하려고 하면 맨 위에 새로운 그릇을 두어야 한다. 이것이 바로 스택이다.스택은 그림과 앞서 말했던 그릇 예시에서 볼 수 있듯이 후입선출(Last-In First-Out: LIFO) 구조를 갖는 자료구조이다. 스택에서는 나중에 들어온 데이터가 처음으로 나가게 된다. 스택의 특징스택의 가장 큰 특징은 후입선출(LIFO) 구조를 갖는다는 것이다. 다른 특징..

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

백준 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..

백준 28278번: 스택 2 https://www.acmicpc.net/problem/28278 28278번: 스택 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 스택에 대한 여러 명령들을 처리하는 문제이다. 스택을 구현하는 데에는 많은 방법들이 있겠지만 이번에는 벡터를 사용했다. 벡터는 push_back함수와 pop_back함수를 사용할 수 있기 때문에 후입선출 구조를 가지는 스택을 구현하기에 적절하다고 생각했다. 벡터는 다양한 함수를 지원하기 때문에 어렵지 않게 구현할 수 있다. 코드 #include #inclu..