2021. 10. 1. 21:20ㆍ카테고리 없음
첫 번째 주제인 스택을 알아보는 글입니다!
자료구조 시간에 배웠거나, 컴퓨터시스템/컴퓨터구조나 프로그래밍 시간에 들어본 등
대부분의 참가자들에게 익숙한 이름일 것 같습니다.
스택의 간략한 개념과 C(C++), Python에서의 사용법, 스택을 사용한 문제를 알아보겠습니다.
최대한 쉽고 간결하게 쓰도록 노력하겠지만,
혹시 이해가 잘 안 된다면 조금 더 자세히 다룬 아래 게시물들을 더 읽어보거나 댓글로 질문해주세요!!
https://blog.naver.com/kks227/220781557098
스택(Stack) (수정 2019-05-14)
또다른 기본 자료구조 중 하나인 스택(stack)입니다. 스택은 LIFO(Last In First Out) 자료구조인...
blog.naver.com
https://justicehui.github.io/easy-algorithm/2018/06/03/StackSTL/
[스택] 스택 STL
서론 이번에는 스택을 구현하기 귀찮을 때 쓰면 좋은 STL을 다룰 것입니다. STL은 stack말고 queue나 deque같은 것도 구현되어 있지만, 그것들은 나중에 해당 자료구조를 할 때 같이 다룰 것입니다. STL
justicehui.github.io
목차
자료구조가 뭔가요..?
다양한 정의가 있지만, 자료구조는 "데이터를 효율적으로 저장/조회/수정/삭제하는 방법"을 말합니다.
수십 년간 프로그램을 만들며 사람들은 많은 프로그램에서 사용되는 비슷한 구조를 찾아냈고,
이런 공통적인 구조를 어디서든 구현하고 사용할 수 있도록 정의한 것이 바로 자료구조입니다.
자료구조를 공부하다 보면 "이런 걸 왜 배우지?" 하는 생각이 들 수도 있는데,
일단 해당 자료구조의 개념을 익히고 여러 활용을 알게 되면 자연스럽게 이해하게 됩니다.
적절한 자료구조를 잘 활용하면 같은 동작이라도 훨씬 빠르게, 효율적으로 수 있다는 점을 생각하면 더 쉽게 공부할 수 있을 것 같습니다!!
스택이란?
스택은 값을 삽입하고, 마지막에 삽입한 값을 읽거나 꺼낼 수 있는 자료구조입니다.
이렇게 접시가 쌓여 있는 모습을 상상해 봅시다.
접시를 하나씩 쌓는다면 가장 나중에 쌓은 접시는 맨 위에 있는 접시일 것입니다.
접시를 꺼낼 때는 맨 위에 있는 접시만 꺼낼 수 있습니다.
굳이 중간 혹은 아래쪽의 접시를 꺼내고 싶다면 꺼내고 싶은 접시 위에 쌓인 접시를 모두 꺼내고,
꺼내고 싶은 접시가 맨 위로 오도록 해야 합니다.
이런 식으로 작동하는 자료구조가 스택입니다.
뭘 할 수 있나요
- 맨 위 값 가져오기
- 맨 위의 값 삭제하기
- 맨 위에 새로운 값 추가하기
- 스택에 들어 있는 값이 몇 개인지 알아보기
스택에 들어 있는 데이터의 수가 아무리 많아져도 위 연산들은 항상 같은 시간에 돌아갑니다.
(상수 시간이 걸린다는 의미입니다. 잘 모르겠다면 이전 게시물을 참고해 주세요)
구현하기에 따라 다른 기능을 더 넣을 수도 있지만, 이 정도의 기능만 있어도 충분합니다.
물론 우리는 이런 기능이 모두 구현된 라이브러리를 사용합니다.
어떻게 쓰나요
C(C++)과 Python에서 사용하는 방법을 소개하겠습니다.
스택을 사용할 때 가장 중요한 것은 빈 스택에서 값을 꺼내거나 읽으면 안 된다는 것입니다.
언어 불문하고 바로 에러가 나기 때문에, 스택에서 값을 꺼내거나 읽을 때는 항상 스택이 비어 있는지 확인해야 합니다.
Python의 경우에는 스택 라이브러리는 따로 없지만,
배열에서 append, pop, len 함수로 위 기능을 모두 구현할 수 있어 그냥 배열을 스택처럼 사용하면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
stk = [] # 빈 스택 만들기
# 스택의 맨 위에 값 추가
stk.append(1) # 현재 스택: 1
stk.append(2) #현재 스택: 1 2
print(stk[-1]) # 스택의 맨 위 값 출력(2)
stk.pop() # 맨 위 값 삭제 / 현재 스택: 1
print(len(stk)) # 스택의 값의 개수 출력(1)
stk.pop()
print(stk[-1]) # 에러(출력할 값이 없음)
|
cs |
C++의 경우에는 <stack> 라이브러리에 스택이 구현되어 있습니다.
C++을 모르더라도 확장자만 .cpp으로 하고 C와 동일한 코드를 작성하면 됩니다.
+ using namespace std; 를 main함수 밖에 한 번 적어주어야 편하게 쓸 수 있습니다
+ 스택 배열을 만들어 여러 개의 스택을 쓰고 싶다면 stack<int> stk[1000]; 처럼 선언하고 stk[10].push(1); 처럼 사용하면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <stdio.h>
#include <stack>
using namespace std;
int main() {
stack<int> stk; // int형을 담는 빈 스택 만들기, char / string 등을 쓰면 해당 자료형을 담게 됨
// 스택의 맨 위에 값 추가
stk.push(1); // 현재 스택: 1
stk.push(2); // 현재 스택: 1 2
printf("%d\n", stk.top()); // 스택의 맨 위 값 출력(2)
stk.pop(); // 맨 위 값 삭제 / 현재 스택: 1
printf("%d\n", stk.size()); // 스택의 값의 개수 출력(1)
stk.pop();
printf("%d\n", stk.top()); // 에러(출력할 값이 없음)
}
|
cs |
Java에서는 java.util.Stack의 Stack 클래스를 이용하면 된다고 합니다
제가 자바를 잘 못해서.. 아래 게시물을 참고하면 좋을 것 같아요
https://coding-factory.tistory.com/601
[Java] 자바 Stack 클래스 사용법 & 예제 총정리
Stack이란? 자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'입니다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. Stack의 가장 큰 특징은 나중에 들어간 것
coding-factory.tistory.com
알고리즘 문제에서 쓰는 방식
알고리즘 문제풀이에서의 스택 문제는 주로
- 마지막에 넣은 순서대로 꺼내야 할 때
- 짝을 맞춰야 할 때(괄호 문자열 등, 응용되면 어려움)
- 단조 스택_monotone stack 사용(어려움)
등의 유형이 있습니다. 이번 대회에서는 쉬운 유형들만 공부해도 충분하지만,
개인적으로 단조 스택을 사용하는 문제들은 정말 신기하고 재밌다고 생각해서 추천하고 싶습니다!
추가적으로 어떤 수식이 문자열로 주어졌을 때 스택을 이용하면 식을 계산할 수 있는데,
관심이 있다면 공부해봐도 좋을 것 같습니다
연습 문제
대망의 연습 문제입니다.
어려운 문제일수록 😿를 많이 달았습니다.
"더보기" 에 풀이를 적었습니다.
스택 실버 문제를 무리없이 풀 수 있다면 본 대회에서도 스택 문제를 풀 수 있을 거라고 예상합니다!!
https://www.acmicpc.net/problem/10828 😿
10828번: 스택
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
스택을 쓸 수 있는지 묻는 문제입니다.
빈 스택에서 값을 꺼내거나 읽으려 하지 않는지 항상 확인해야 합니다.
잘 모르겠거나 계속 틀린다면 정답 코드를 참고하세요
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
어떤 수를 원하는 순서에 뽑으려면 자신보다 먼저 뽑혀야 하는 수들이 이미 들어갔다가 모두 뽑힌 상태여야 합니다.
따라서 스택에 1부터 N까지의 수를 차례대로 넣으면서 스택의 맨 위 값이 뽑아야 할 값이면 뽑는 것을 반복하고, 이렇게 모든 수를 넣었다 뺄 수 있으면 가능, 못 빼는 수가 생기면 불가능합니다.
https://www.acmicpc.net/problem/1406 😿😿
1406번: 에디터
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수
www.acmicpc.net
커서의 앞부분과 뒷부분을 각각 스택으로 생각해 봅시다.
커서와 가까운 문자일수록 각 스택의 윗쪽에 오게 하면
커서가 앞으로 이동하면 앞부분 스택의 맨 위 문자를 뒷부분 스택에 넣고, 앞부분 스택의 맨 위를 삭제하면 됩니다.
비슷한 원리로 모든 연산을 스택으로 구현할 수 있습니다.
https://www.acmicpc.net/problem/1935 😿😿😿
1935번: 후위 표기식2
첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이
www.acmicpc.net
주어진 식을 앞에서부터 한 글자씩 보면서 피연산자(ABCD..)라면 해당하는 값을 스택에 넣고, 연산자(+-*/)라면 맨 위의 값 두 개를 꺼내서 연산 결과를 스택에 넣으면 됩니다. 최종적으로 스택에 남아 있는 값이 계산 결과입니다.
C(C++) 정답: http://boj.kr/361e93e3d5f241bd9fa6ba6fd7501107
우리가 보통 쓰는 3+2-5 와 같이 연산자가 피연산자 사이에 있는 중위 표기식을 후위 표기식으로 변환하는 것도 스택으로 할 수 있는데, 궁금한 분들은 더 공부해보시길 바랍니다.
https://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
주어진 순서대로 스택에 수를 넣으면서 스택에 들어 있는 수들을 위에서부터 보았을 때 비내림차순이도록 유지한다고 생각해 봅시다.
비내림차순을 유지하려면 새로 스택에 수를 넣을 때 스택의 맨 위에 넣을 수보다 작은 수가 있으면 안 되므로, 조건에 맞지 않는 수를 모두 뽑고 수를 넣어야 합니다.
스택에 들어 있던 수 입장에서는 자신 오른쪽에 있는 수 중 자신보다 큰 수가 스택에 들어오는 순간 빠져나가게 됩니다. 따라서 이렇게 각 수의 오큰수를 찾을 수 있습니다.
이중 반복문이 있어 $O(N^2)$ 시간이 걸리는 것 같지만, $N$개의 수가 한 번 들어왔다가 한 번 나가기 때문에 $O(N)$ 시간이 걸립니다.
이렇게 스택에 들어 있는 수들이 오름차순/내림차순 등의 성질을 만족하도록 유지시키는 스킬을 "단조 스택" 또는 "monotone stack" 이라고 합니다.
https://www.acmicpc.net/problem/6549 😿😿😿😿😿😿😿😿
이런 건 못 풀어도 되지만,, 오큰수 문제가 너무너무 쉬웠다면 한 번 도전해보세요
만약 온전히 혼자 힘으로 풀었다면 꼭 좋은 선생님 구해서 정보올림피아드를 나가야 합니다
6549번: 히스토그램에서 가장 큰 직사각형
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤
www.acmicpc.net
오큰수 문제를 응용하면 각 직사각형마다 왼쪽/오른쪽에서 자신보다 작으면서 가장 가까운 직사각형을 찾을 수 있습니다. 이를 이용하여 각 막대를 완전히 포함하는 직사각형의 너비와 최대 넓이를 찾을 수 있고, 이렇게 찾은 직사각형 넓이의 최댓값이 정답입니다. 정답 코드는 생략하겠습니다.