[실전 알고리즘] 0x05강 - 스택

 

안녕하세요, 오늘은 스택을 조져보려고 합니다. 이번 시간부터 세 단원 동안 스택, 큐, 덱을 다룰건데 셋 다 비슷비슷해서 하나만 익히고 나면 전반적으로 어렵지않고, 내용 자체도 연결리스트보다는 더 할만합니다. 

 

늘 그렇듯 정의와 성질과 기능과 구현을 배우고 또 STL도 배울 것입니다.

 

이미 자료구조의 스택을 알고 있는 분은 어쩔 수 없고, 다른 분들은 스택이라는 말을 들으면 뭐가 제일 먼저 생각이 나세요? 저는 롤을 좋아해서 그런지 나서스 스택이랑 베이가 스택이 먼저 생각납니다. 

 

네, 쓸데없는 소리였고, 쟤네들의 스택이나 자료구조에서의 스택이나 같은 단어인건 맞는데 크게 의미는 없는 것 같습니다. 

 

그러면 자료구조에서의 스택은 뭐냐하면, 바로 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조입니다. 대충 프링글스 통을 생각하면 이해가 쉬울 것입니다. 아니면 엘리베이터를 생각해도 되겠습니다.

 

스택은 구조적으로 먼저 들어간 원소가 제일 나중에 나오게 되는데, 이런 의미로 FILO(First In Last Out) 자료구조라고 부르기도 합니다. 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있습니다. 그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 합니다.

 

스택은 특정 위치에서만 원소를 넣거나 뺄 수 있게 제한을 둔 대신에 원소의 추가와 제거가 모두 O(1)입니다. 나중에 구현을 같이 해보겠지만 우리가 배열의 끝에서 원소를 추가/제거할 때 시간복잡도가 O(1)이었던 것과 완전 상황이 똑같습니다. 그리고 제일 상단의 원소 확인 또한 O(1)입니다.

 

대신 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능합니다. 원칙적으로 불가능하다는 뜻을 잘 이해할 필요가 있는데, 원래 스택이라는 자료구조는 원소의 추가/제거/제일 상단의 원소 확인이라는 기능만 제공하는 자료구조입니다. 그래서 제일 상단이 아닌 나머지 원소들의 확인/변경은 스택에서 제공하는 기능이 아닙니다. 구현을 할 때 배열을 기반으로 구현해서 해당 기능이 가능하도록 만들 수는 있지만, 나중에 스택의 응용 사례들을 보시면 모두 원소의 추가/원소의 제거/제일 상단의 원소 확인 기능만을 필요로 합니다.

 

그래서 정리를 하면, 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않습니다. STL stack에서도 이 기능은 없습니다. 그리고 스택을 활용하는 예시들을 보면 애초에 제일 상단이 아닌 나머지 원소들의 확인/변경이 필요하지 않습니다. 하지만 배열을 이용해 스택을 구현하면 기본적인 스택의 기능 이외에도 제일 상단이 아닌 나머지 원소들의 확인/변경을 가능하도록 만들 수는 있습니다.

 

스택에서 제공되는 연산들을 살펴봤으니 그 다음으로 스택을 어떻게 구현하면 될지 알아보겠습니다. 스택은 배열 혹은 연결 리스트를 이용해서 구현할 수 있습니다. 그리고 둘 중에서 배열을 이용하는게 구현이 더 쉽습니다.

 

물론 연결 리스트를 연습하는 차원에서는 연결 리스트로 구현을 시도해봐도 좋지만 여기에서는 배열을 이용한 구현만 다루도록 하겠습니다.

 

스택을 배열로 구현할 때에는 단지 원소를 담은 큰 배열 한 개와 인덱스를 저장할 변수 한 개만 필요합니다. 이들이 실제 스택에 어떻게 대응되는 방식을 확인해보면 오른쪽 그림과 같습니다.

 

{13, 21, 30}이 담겨있는 스택을 나타내기 위해 dat[0], dat[1], dat[2] 각각에 13, 21, 30을 썼고 pos는 3이라는 값을 가집니다. 이와 같이 스택의 값들은 dat의 0번지부터 저장되고 pos는 다음에 원소가 추가될 때 삽입해야하는 곳을 가리키고 있습니다. 그리고 잘 생각해보면 pos의 값이 곧 스택의 길이, 즉 스택 내의 원소의 수를 의미한다는 것을 알 수 있습니다.

 

이제 스택을 직접 구현해보겠습니다. 조금 막막할 수 있겠지만 곰곰히 생각해보면 정말 쉽습니다. 진짜 정말로 쉽습니다. 그래서 한 번 시도해보시면 좋겠습니다. 구현체를 빼놓은 template는 github 링크에서 확인할 수 있습니다.  

 

push 함수는 스택에 x를 추가하는 함수이고, pop 함수는 스택의 꼭대기에 위치한 원소를 제거하는 함수이고, top 함수는 스택의 꼭대기에 위치한 원소의 값을 확인하는 함수입니다. 다음 슬라이드에서 push 함수부터 차례로 구현을 해보겠습니다.

 

제가 진짜 괜히 엄청 쉽다고 말을 한게 아닌데, 아무튼 지금 왼쪽 스택에서 원소 12를 넣고싶다고 해보겠습니다. 그러면 어떤 작업을 해야하는지 직관적으로 눈에 딱 보일텐데 pos가 가리키는 자리에 12를 추가하고 pos를 1 증가시키면 됩니다. 그리고 이건 코드 한 줄로 표현할 수 있습니다. push는 아주 EZ하네요.

 

그 다음으로는 꼭대기에 있는 12를 빼보겠습니다. 12를 빼려면 딱 1개만 하면 되는데 그냥 pos를 1 줄이면 됩니다. 이 때 dat의 3번지에 있는 값 12 자체는 굳이 변경하지 않아도 괜찮습니다. 왜냐하면 나중에 push가 발생하면 어차피 그 때 들어올 값으로 덮어써질거라 더 이상 저 12라는 값은 아무 의미가 없고, 이런 상황이면 굳이 값을 변경하는 추가적인 연산을 하는게 시간낭비니 내버려두면 될 것입니다. 이를 코드로 표현하면 pos--; 입니다.

 

제일 위의 원소를 확인하는 top 함수는 더욱 더 날먹일 것 같은데, 지금 이런 상황에서 12를 반환하고 싶으면 진짜 그냥 dat[pos-1]만 반환하면 끝입니다. 코드도 뭐 곧이곧대로 옮기면 끝이죠.

 

이렇게 push, pop, top 함수가 모두 한 줄로 구현이 되는 것을 볼 수 있습니다. 전체 코드는 github 링크에서 확인할 수 있습니다.

 

stack은 이처럼 구현이 특출나게 간단하지만, 그래도 STL을 쓸 수 있다면 STL을 쓰는게 좋습니다. 내가 만든 스택을 썼는데 다 짜고 돌렸더니 틀렸다고 할 때, 이러면 내가 만든 스택에 틀린 점이 있는지 의심을 해볼 수 밖에 없게 됩니다. 그런데 STL stack을 썼으면 최소 스택 쪽에서는 문제가 없다는걸 알 수가 있으니 로직을 바로잡는게 조금이나마 더 편할 것입니다.

 

그래서 STL stack을 익히는 차원에서 예제를 한 번 살펴보겠습니다. STL stack에서는 주로 push, pop, top, empty, size 멤버 함수를 쓰게 될 것입니다. push, pop, top은 우리가 앞에서 한거랑 똑같고, empty랑 size도 크게 어렵지 않을 것입니다.

 

그리고 18번째 줄을 보면 알겠지만 스택이 비어있는데 top을 호출하면 런타임 에러가 발생합니다. 스택이 비어있는데 pop을 호출해도 마찬가지입니다. 그렇기 때문에 스택이 비어있을 때에는 top이나 pop을 호출하지 않도록 해야합니다. 또 제출한 코드의 결과로 런타임 에러를 받았을 경우에는 다양한 원인이 있을 수 있겠지만 스택이 비어있을 때 top이나 pop을 하지는 않았을지 의심해볼 수 있습니다.

 

이번에는 연습문제를 풀어보겠습니다. 첫 번째 연습문제는 BOJ 10828번: 스택 문제입니다. 문제를 확인해보시면 그냥 곧이곧대로 스택을 구현하라는 문제라는 것을 알 수 있습니다. STL stack과 직접 구현한 스택 두 가지 모두를 가지고 해결해보세요.

 

>먼저 STL stack을 이용한 풀이를 설명드리겠습니다. 코드에서 크게 어려울 건 없을 것입니다. 단 pop, top 함수에서 S가 empty인지 확인을 먼저 하고 S.pop()이나 S.top()을 호출해야 합니다. 그렇지 않으면 런타임 에러가 발생할 수 있습니다.

 

두 번째로 직접 구현한 스택을 이용해보겠습니다. 일단 push, pop, top 코드들을 가져다 쓰는데 문제에 있는 "스택에 들어있는 정수가 없는 경우에는 -1을 출력한다"와 같은 조건들에 대한 처리를 잘 해주면 됩니다. 마찬가지로 크게 어렵지는 않을 것입니다.  

 

코드를 확인해보세요. pos=0이면 스택이 비었다는 의미이니 pop, empty, top일 때 이를 잘 활용했습니다.

 

이번건 분량이 그다지 많지 않아서 수월했을 것 같습니다. 지금까지 배열, 연결 리스트, 그리고 스택 자료구조를 배웠는데, 스택부터는 본격적으로 활용을 할 수 있는 방법이 굉장히 많아집니다. 대표적인 사례로 수식의 괄호 쌍이랑 전위/중위/후위 표기법, DFS, Flood Fill 등이 있습니다. 각 사례들은 학부 수업에서 웬만하면 다 짚고 넘어갈 내용들이라 배울 필요가 있는데, 이번 단원 안에서 전부 설명을 하기에는 분량이 꽤 많아서 각 내용들을 독립적인 단원으로 만들어서 설명할 것입니다. 단, 전위/중위/후위 표기법은 코딩테스트에 나올 확률이 0에 가깝다고 판단해서 아예 패스합니다.

 

연습문제들에는 스택을 이용해서 풀 수 있는 문제들을 넣어뒀는데 10773번은 그럭저럭 풀만하지만 나머지 문제들은 다소 생소할 발상을 필요로 하기 때문에 좀 많이 어려울 것입니다. 그래서 10773번을 제외한 나머지 문제들은 어렵다 싶으면 굳이 얽매이지말고 일단 넘어가셨다가 BFS/DFS를 다룬 후에 보셔도 괜찮습니다.

 

그럼 고생 많으셨고 다음 단원에서 만나요. 

  Comments
  • th택 가즈앗
    제 추천문제가 문제집에 들어가 있군요 ㅎㅎ
  • 연습문제들은 어디서 볼수있나요?
  • HDK
    나서스 스택과 베이가 스택 강의 잘보았습니다~ㅎㅎㅎ
  • question
    직접 구현하는 스택에서 pos가 0인상태에서 pop()을 하고 top()을 하면 dat[-1]로 잘못된 인덱스로 접근하는거 아닌가요??
    근데 실제로 돌려보니까 오류도 발생하지 않고 답도 정상적으로 나오는데 왜 그런지 이해가 안됩니다..
    • C언어에서는 잘못된 인덱스에 접근했다고 해서 무조건 오류가 발생하는건 아닙니다.

      다만 잘못된 인덱스에 접근하는 코드를 제출해서 여러 테스트케이스에 돌리다보면 높은 확률로 런타임에러가 발생합니다.
  • mdr
    1874번에서 올려주신 정답 코드에서 line 24에 return 0; 하는 부분 대신 break;로 수정했었는데 출력초과가 뜨던데 이유가 궁금합니다.
    함수는 무조건 어떤 값을 반환하므로 값을 반환해주어야 하는데 break;로 변경할 경우 while문은 종료되나 반환되는 값이 없어 반화될때까지 함수가 종료되지 않기 때문인가요?
    void 함수() 이런 형태여도 return으로 함수의 종료를 알려줘야하는게 맞는건가요?
  • jcreate98
    stack 문제 모아두신 문제집을 풀다가 히스토그램에서 막혀서 질문 드립니다.

    https://www.acmicpc.net/board/view/83839

    https://bingorithm.tistory.com/14 < 여기 다른 이용자 분이 정리해주신 반례 모두 통과해서 제출했는데 오답 판정 받았습니다.

    데이터 오버플로우가 나거나 이상한 값이 들어가나 여러 번 읽어봤는데 어디서 잘못됐는지 못 찾겠습니다..
    틀린 부분이 있다면 힌트주시면 감사하겠습니다!
    • 반례
      3 1 2 5
      3 5 2 5
      0

      이것저것 넣어보다가 반례 찾았는데 스택 초기화 관련 문제인건가 싶네요. 한 번 확인해보세요
    • 반례 보고

      https://www.acmicpc.net/board/view/83890
      히스토그램 단독 문제 있어서 여기서 반례 처리 해서 풀어봤습니다

      stack 에 최솟값이 들어올 때 index에 문제가 있는 것 같아서 pop할 때 계산해봤는데 반례는 잘 처리하는데 오답으로 나옵니다..
      혹시 index 사용하는게 아닌가요..?
    • 일단 반례는

      3
      3 2 1입니다.

      그와 별개로 사족을 좀 달자면 저도 몇년간 ps 공부에 매진했던 입장에서 특히 맞왜틀을 당했을 때의 막막함에 대해 잘 알고 있고 지금 jcreate98님이 겪고 있을 고통에 대해 공감합니다.

      하지만 지금 코드의 로직을 잘 따라가지 못하겠고, 그냥 이것저것 값을 넣어보다가 얻어걸리면 알려드리는 식으로 하고 있어서 이건 엄청 특별한 방법론이 필요한게 아니라 jcreate98님도 스스로 충분히 할 수 있는 일이라고 생각합니다.

      일단 monotone stack을 활용하는 풀이의 흐름은 대략적으로 맞는 것 같은데 29-61 line에서 불필요하게 if/else로 코드의 로직이 복잡하게 나눠져있어 너무 코드 분석을 어렵게 만들고 또 (꼭 필요한 일이라면 하겠다만)선뜻 손이 가지도 않습니다.

      이미 충분히 시도를 해보신 것 같으니 아래와 같은 방식으로 도전을 해보는게 어떨까요?

      1. 정답 코드( https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x05/solutions/6549.cpp )를 확인해보시면 29-61 line의 로직이 21-27 line으로 많이 간소화되어 있습니다. 정답 코드를 참고해서 로직을 잘 정리해보세요.

      2. 매 for문마다 stack의 전체 값을 출력해서 스택에 내가 의도한대로 값이 들어가는지 확인해보세요.

      이 두가지를 해보고도 여전히 답이 틀린다면 다시 댓글 주세요.
    • 흐름은 맞지만 너무 불필요하게 꼬여있다 하셔서 그냥 다 밀어버리고 처음부터 스택 출력하면서 풀어보니까 잘못된 부분 찾았습니다..

      반례가 계속 나오니까 코드 고칠 생각은 안하고 반례 처리할 생각만 해서 코드만 길어지고 고치기 힘들어졌던 것 같습니다.

      귀찮게 해서 죄송하고 다음 강의 듣다가 궁금한 부분 생기면 다시 오겠습니다!
      감사합니다!
  • 6198번 옥상 정원 꾸미기를 풀다가 의문점이 생겨 질문합니다!

    거의 정답코드와 유사한 로직으로 풀었는데 정답코드 22번 라인의 while문 조건을
    while(s.top() <= h && !s.empty()) 로 제출했더니 런타임에러(Segfault)가 발생했습니다.

    런타임에러가 발생한 이유가 무엇인가요?
  • PSLOVER
    p. 13 산 이미지 넘 예쁘네요 ㅋㅋ 강의 잘 들었습니다. 감사합니다.
댓글 쓰기