스택(stack)
Last updated
Last updated
자료 구조
스택과 관련된 내용
현재 자료구조 시간에서 스택과 큐를 배우는 주차라 수업과 동시에 배우는 것이 좋아 보여서 5주차에 넣었습니다.
알고리즘에서 스택을 이용하여 문제를 푸는 방법은 직접 스택을 구현해서 푸는 것이 아니라, 각 자료구조의 특징을 이용하여 이미 만들어진 메소드를 이용하여 문제를 풀고 있기 때문에 아직 자료구조를 배우지 않은 1학년분들도 쉽게 따라올 수 있습니다.
참고로 C++을 아시는 분들은 KOALA 회장님이 지난 겨울 방학 때 진행한 알고리즘 기초 스터디 영상도 있으므로 참고하시면 좋을 것 같습니다.
스택은 값이 들어가는 입구와 나가는 출구가 같은 자료구조 입니다. 그래서 마지막으로 들어간 값이 첫 번째로 나오는 Last In First Out(LIFO)구조를 가졌습니다.
이게 무슨 소리인지 그림들을 통하여 살펴봅시다.
이렇게 아래가 막혀있고, 위가 뚫려있는 상자가 있을 때, 값이 들어가는 곳과 나오는 곳이 같으므로 이것은 스택입니다. 이 그림을 보면 알 수 있듯이 가장 먼저 들어가는 값이 맨 아래로 들어가서 차곡차곡 쌓이게 됩니다. 생긴 것이 상자에 물건을 넣을 때와 비슷하게 생겼습니다.
이렇게 4번 상자까지 스택에 들어갔다고 가정할 때, 들어가는 입구와 출구가 같기 때문에 값이 빠져나가는 과정은 아래 사진처럼 4 → 3 → 2 → 1이 되겠네요.
스택을 이용한 알고리즘 문제를 풀 때 알고 있어야 하는 특징은 이게 끝입니다. 스택 자료구조는 LIFO이다, 마지막 값이 제일 먼저 들어간다, ... 이런 내용을 외울 필요 없이 한쪽이 열려있는 상자와 박스 모양 그림만 떠올리면 됩니다.
스택은 리스트(list)로 만들 수 있습니다. 리스트의 메소드를 이용하여 만들 수 있는데 바로 append() 메소드와 pop() 메소드입니다. 이 메소드들은 이미 우리가 2주차에서 배우고 계속 사용하고 있었습니다. 이것을 그냥 스택처럼 생각해서 이용하면 됩니다.
위에 있는 그림을 코드로 만들어봅시다.
이렇게 값을 추가해주면 오른쪽 끝에 값이 추가되는 것을 확인할 수 있습니다.
이제 값을 빼는 코드를 만들어봅시다.
마찬가지로 값을 빼줄 때도 오른쪽 끝에서 값이 빠져나오는 것을 확인할 수 있습니다. 간단하죠?
다른 기능들은 아래 문제를 통해 풀어봅시다.
스택은 5가지 명령을 가지고 있다고 합니다.
일단 입력값을 받는 코드를 만들기 전에 예제1 입력 값부터 살펴봅시다.
top, size, empty, pop은 전부 입력 값이 한 개이지만, push 1과 push 2와 같이 push는 입력 값이 2개로 이루어져 있습니다.
그래서 입력 값을 리스트로 받아서 push, top, size, empty, pop은 arr[0]로 받고, push다음에 들어오는 값은 arr[1]로 받을 수 있겠네요.
이제 입력 값을 받는 코드를 만들어봅시다. 이 문제는 일단 빠른 입력을 필요로 합니다.
이제 본문에 설명된 순서인 push, pop, size, empty, top 순서대로 만들어봅시다.
push X는 입력 값이 2개이고, X는 숫자값이므로 arr[1]의 값을 int형으로 바꿔야 한다는 생각이 들 수 있습니다. 하지만 여기서는 스택에 넣는 값 가지고 다른 연산을 하지 않기 때문에 굳이 int형으로 바꾸지 않아도 될 것 같네요.
push 기능은 스택에 X 값을 넣어주는 것이므로 append 메소드를 이용하여 만들어주면 됩니다.
pop은 위에서 배운 내용대로 pop 메소드를 사용하면 됩니다. 그리고 스택에서 뺀 정수를 출력하는데, 만약 스택에 뺄 정수가 없으면 -1을 출력하라고 합니다.
이것은 len()함수를 통하여 len(stack)이 0이면 -1을 출력, 아니면 stack.pop()을 출력하면 됩니다.
스택에 들어있는 정수의 개수를 출력하라고 합니다.
스택에 들어있는 정수의 개수, 즉 요소의 개수를 출력하라는 말인데요. 이것도 pop에서와 마찬가지로 len()함수를 통하여 출력할 수 있습니다.
스택이 비어있으면 1, 아니면 0을 출력하라고 합니다. 이것도 len()함수를 이용하여 만들 수 있습니다.
마지막으로 top은 스택의 가장 위에 있는 정수를 출력하라고 합니다. 예제 1 출력 값을 보니 push 1, push 2, top을 입력하면 2를 출력하고 있습니다. 이것은 우리가 스택의 특징을 배울 때 봤던 위가 뚫려있는 상자에서 맨 위 값을 출력하면 될 것 같습니다. 리스트에서는 맨 오른쪽의 값을 출력해야겠네요.
그리고 스택에 정수가 없을 때는 -1을 출력하라고 합니다. 이것도 len()함수를 이용하여 만들 수 있습니다.
이렇게 코드를 완성하면 끝입니다.
이제 스택을 이용한 문제를 풀어보겠습니다.
아치형 곡선을 그리는데, 선끼리 교차하지 않고 A는 A끼리, B는 B끼리 쌍을 지을 수 있다면 그 단어는 좋은 단어라고 합니다.
아치형 곡선인데 선끼리 교차하지 않는다는 것은 예제 1을 그림으로 그려보면 아래와 같습니다.
ABAB는 선끼리 교차하므로 좋은 단어가 될 수 없고, AABB는 AA, BB곡선이 따로 떨어져 있으므로 교차하지 않으니 좋은 단어, ABBA는 BB위에 AA곡선이 있지만 둘이 교차하지 않으므로 좋은 단어 입니다.
이걸 보니까 문자 A가 나오면 스택 맨 위 값이 A일 경우 stack.pop()을 해주고, 문자 B가 나오면 스택 맨 위 값이 B일 경우 stack.pop()을 해주면 되겠네요. 그게 아니라면 전부 append()로 추가해주면 될 것 같습니다.
이제 입력 값을 받아봅시다.
이제 스택에 값을 넣어야 하는지, 빼야 하는 결정하려면 문자를 확인할 때, 맨 위 값을 비교하여 append를 사용할지, pop을 사용할지 결정해야겠죠?
이것은 stack[-1]을 통해 확인할 수 있습니다. 그런데 스택에 값이 들어있지 않으면 stack[-1]을 사용할 때 오류를 출력하므로 if문을 이용하여 stack에 값이 있는지 없는지 확인해봐야 합니다.
그래서 스택에 값이 들어있으면 stack[-1]을 사용해서 진행하고, 없으면 무조건 append를 이용하여 값을 넣어줘야겠네요.
이제 문제에서 요구하는 구현은 끝났고, ans변수를 통하여 좋은 단어의 개수를 출력해야 합니다. 좋은 단어일 경우 스택이 비어있으므로 len()함수를 이용해 ans += 1을 해주고, 마지막에 ans를 출력을 해주면 됩니다.
풀어볼 문제
