2강 자료구조 1 - 스택

 

우오와

 

자료구조 1 강의에서는 크게 스택, 큐, 덱에 대해 배우는데 스택을 주로 다루고 큐와 덱은 그래프(BFS)에서 자세하게 다룬다고 한다.

 

<스택>

스택(Stack)이란 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다. LIFO(Last in First Out)라고도 부른다. 그래서 나중에 들어간 데이터가 제일 먼저 나올 수 있다.  

스택 자료구조

위의 그림처럼 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조로 마지막으로 넣은 것이 가장 먼저 나오기 때문에 LIFO라고 한다. 따라서 만약 데이터를 저장하고 가운데에 저장한 데이터를 pop해야 하는 연산이 필요하다면 이는 스택을 사용하면 안되는 알고리즘이다. 다음은 스택 연산이 종류이다.

 

- push : 스택에 자료를 넣는 연산

- pop : 스택에서 자료를 빼는 연산

- top : 스택의 가장 위에 있는 자료를 보는 연산

- empty : 스택이 비어있는지 아닌지를 알아보는 연산

- size : 스택에 저장되어 있는 자료의 개수를 알아보는 연산

 

스택은 배열의 인덱스와 같이 0부터 시작하기 때문에 만약 스택의 size가 5라면 stack에는 stack[0] ~ stack[4]까지 채워져 있는 것이다. 아래는 스택과 관련된 예제이다.

 

 

<10828번 / 스택>

- 스택을 구현하는 문제 

- 이 문제에서는 스택을 직접 구현하지만 이미 라이브러리에 스택이 구현되어 있다. 따라서 c++에서는 std::stack, Java에서는 stack, python에서는 list 라이브러리를 사용하면 된다. 지금은 스택을 연습해야 하기 때문에 직접 구현해보자!

이 코드에서 우선 Stack 구조체를 선언하고 구조체 멤버로는 자료를 저장할 int형 배열과 스택의 사이즈인 int형 변수를 선언하고 스택 연산을 위한 4개의 함수가 존재한다 - push, empty, pop, top

그리고 main함수에서는 테스트 케이스만큼 while 반복문을 통해 명령을 실행하고 입력받은 명령어를 기준으로 조건문을 통해 나누어 실행한다. 조건문 내에서는 해당 명령어에 해당하는 함수를 호출하여 동작을 시행하고 출력하였다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

#include <iostream> #include <string> #include <stack> using namespace std; typedef struct Stack {     int data[10000];     int size;     Stack() {         size = 0;         data[10000] = 0;     }     void push(int num)     {         data[size] = num;         size += 1;     }     int empty()     {         if (size == 0)             return 1;         else             return 0;     }     int pop()     {         if (empty() == 1)         {             return -1;         }         else         {             size -= 1;             return data[size];         }     }     int top()     {         if (empty() == 1)             return -1;         else         {             return data[size - 1];         }     } }S;   int main(void) {     cin.tie(NULL);     ios_base::sync_with_stdio(false);     int n = 0;     cin >> n; //명령의 수     S s;     while (n--)     {         string cmd;         cin >> cmd;         if (cmd == "push")         {             int num;             cin >> num;             s.push(num);         }         else if (cmd == "pop")         {             cout << s.pop() << '\n';         }         else if (cmd == "size")         {             cout << s.size << '\n';         }         else if (cmd == "empty")         {             cout << s.empty() << '\n';         }         else if (cmd == "top")         {             cout << s.top() << '\n';         }     }     return 0; }

cs

 

첫번째 코드를 작성하고 제출했을때 채점 시간이 너무 오래걸렸다. 그래서 전 시간에 배운 ios_base::sync_with_stdio(false); 와 cin.tie(NULL); 을 추가하였더니 확실히 속도가 빨라졌다! 히히 'ㅅ'

 

 

<9093번 / 단어 뒤집기>

다음으로는 스택 자료구조를 활용한 단어 뒤집기 문제이다. 

 

- 문장이 주어졌을 때 단어를 모두 뒤집는 문제

- 단어의 순서를 바꿀 수 없고, 단어는 영어 알파벳으로만 이루어져 있다.

- 단어의 최대 길이 : 20, 문장의 최대 길이 : 1000

- 단어는 공백 기준으로 구분되며 한 단어내에서만 뒤집으면 된다.

 

이 문제는 N개의 글자를 스택에 넣었다가 뺴면 순서가 역순이 되기 때문에 스택 구조를 사용하기 최적화되어 있다. 그래서 이건 알파벳을 스택에 넣고, 공백이나 문자열의 끝이면 스택에서 모두 빼내서 역순을 만들면 된다. 이 문제의 시간 복잡도는 push/pop의 시간 복잡도가 O(1)이기 때문에 N개의 글자일 때 O(N)이 된다. 

 

그리고 여기서 주어진 예시 코드에서 cin.ignore() 라는 함수가 쓰이는 데 잠깐 이 함수에 대해 알아보쟈!

 

- cin.ignore()

C++에서 ignore는 입력 버퍼를 비워주는 역할을 한다. cin을 통해 문자를 입력받을 경우 바로 변수에 값이 저장되는 것이 아니라 입력한 문자가 먼저 입력 버퍼에 저장되고, 버퍼에 저장된 값을 읽어들여 변수에 저장한다. 하지만 숫자를 입력받는 경우에는 바로 변수에 저장되어 버퍼가 필요하지 않다. 

그런데 만약 cin을 통해 숫자를 입력받아 정수형 변수에 바로 저장하는 도중, 문자가 입력되면 그 문자는 입력버퍼에 저장되고 cin을 통해 이 입력버퍼에 있는 값을 읽어들여 정수형 변수에 저장하려고 하기 때문에 정상적으로 저장되지 않고 계속 failbit을 설정하며 버퍼에도 값이 계속 남아있게 된다고 한다. 

(*failbit : 보통 입력 작업 시 내부적인 논리 오류로 인해 발생되는 오류로, 입력 받기를 기대했던 값이 아닐 때 설정된다.)

failbit는 clear함수를 통해 초기화가 가능하지만 입력 버퍼는 비워지지 않아 이로는 해결할 수 없다. 따라서 cin.ignore 함수를 통해 입력버퍼를 비워주면 된다!

 

- cin.clear()

이는 cin 객체의 내부 상태 플래그를 초기화한다. 

 

- cin.fail()

I/O 에러가 발생하면 true를 반환한다.

 

예제 코드에서는 cin을 통해 테스트 케이스를 입력받고 문자열을 입력받게 되는데 getline은 개행 문자까지를 입력받는데 테스트 케이스를 입력할 때 개행문자가 입력되지 않는다. 그러면 getline에서 첫번째 문자열이 빈 문자열이 되기 때문에 cin.ignore()를 통해 이를 방지해준다고 한다...뭔말이여...

아래는 cin.ignore를 사용하지 않았을 때다. 그러니까 진짜 첫번째 문자열이 빈문자열이었다. 와우... 

 

ignore 사용안한 경우

암튼 이번엔 내가 직접 구현해보록 하겠슴둥~~

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <iostream> #include <string> #include <stack> using namespace std;   int main(void) {     ios_base::sync_with_stdio(false);         cin.tie(NULL);     int t;     cin >> t;     cin.ignore();     for (int i = 0; i < t; i++)     {         string str;         getline(cin, str);         str += '\n';         stack<char> s;         for (int j = 0; j < str.length(); j++)         {             if (str[j] == ' ' || str[j] == '\n')             {                 while (!s.empty())                 {                     cout << s.top();                     s.pop();                 }                 cout << str[j];             }             else             {                 s.push(str[j]);             }         }     }     return 0; }

cs

따란~ 스택으로 구현했다! 희희'ㅅ' 확실히 스택으로 하니까 편한것 같다!

 

 

<9012번 / 괄호>

- 괄호 문자열이 주어졌을 때, 올바른 괄호 문자열인지 아닌지를 알아보는 문제

- 이 때 괄호 문자열은 (와 )로만 이루어진다.

- 올바른 괄호 문자열 : 괄호의 쌍이 올바른 문자열

 

이 문제또한 스택을 사용해서 올바른 괄호 문자열인지 아닌지를 알 수 있다. 이 문제를 해결하기 위해서는 (가 나오면 스택에 (를 넣고 )가 나오면 스택에서 하나를 빼서 (인지 확인한다. 또는 하나를 뺄 수 있는지를 확인하면 된다!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include <iostream> #include <string> using namespace std; string decide(string str) {     int size = 0;     for (int i = 0; i < str.length(); i++)     {         if (str[i] == '(')         {             size++;         }         else         {             size--;         }         if (size < 0)         {             return "NO";         }     }     if (size == 0)         return "YES";     return "NO"; } int main(void) {     ios_base::sync_with_stdio(false);         cin.tie(NULL);     int t;     cin >> t;     while (t--)     {         string str;         cin >> str;         cout << decide(str) << '\n';     }     return 0; }

cs

이 문제는 괄호 문자열이기 때문에 그냥 (면 size를 1 증가하고 )면 size를 1 감소한다. 만약 size가 0보다 작아지면 (가 부족한거므로 NO를 리턴한다. 반복문이 끝나면 size를 체크한다. size가 0이면 (와 )의 개수가 맞는 것이므로 YES, 아니면 NO를 리턴하면 된다. 이 문제의 기본적인 알고리즘은 스택이지만 비교만 하면 되기 때문에 굳이 스택에 넣을 필요는 없기 때문에 이와 같이 구현하였다.

 

 

<1874번 / 스택 수열>

n은 테스트 케이스, m은 스택에 넣을 숫자, x는 현재 입력받은 숫자이다. string형 변수인 res에 결과를 저장한다. push를 할 땐 res에 +를, pop을 할 땐 -를 저장한다. x가 m보다 크면 int형 스택인 s에 m을 push하면서 m을 1씩 증가한다. 여기서 내가 헷갈려서 s.push(m++)로 했는데 이러면 m이 먼저 커져버리기 때문에 잘못된 코드가 된다. 이 점 주의!! x가 m보다 작을땐 스택에서 pop을 하여 x와 비교하고 같으면 true, 다르면 false이다. 만약 false라면 NO를 출력하고 바로 return해버린다. 연산이 모두 끝나면 반복문을 통해 저장된 문자열을 한글자씩 출력한다. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include <iostream> #include <string> #include <stack> using namespace std; int main(void) {     int n;     cin >> n;     int m = 0;     stack<int> s;     string res;     while (n--)     {         int x;         cin >> x;         if (x > m)         {             while (x > m)             {                 s.push(++m);                 res += '+';             }             s.pop();             res += '-';         }         else         {             bool found = false;             if (!s.empty())             {                 int top = s.top();                 s.pop();                 res += '-';                 if (top == x)                 {                     found = true;                 }             }             if (!found)             {                 cout << "NO" << '\n';                 return 0;             }         }     }     for (int i = 0; i < res.size(); i++)     {         cout << res[i] << '\n';     }     return 0; }

cs

 

<1406번 / 에디터>

이 문제를 문자열로 구현하게 된다면 문자열의 길이가 M일 때 연산 하나당 시간 복잡도는 O(M)이 되어서 전체 문자열의 시간 복잡도는 O(M^2)이 된다. 그러면 너무 오래 걸리게 된다. 하지만 스택을 사용하여 수행하게 된다면 명령 하나당 시간 복잡도는 O(1)이고 전체 문자열의 시간 복잡도는 O(M)이 되기 때문에 스택으로 구현하는 것이 훨씬 효율적이다. 

이는 커서를 기준으로 왼쪽 스택과 오른쪽 스택으로 나눠서 구현하면 된다. 왼쪽 스택에는 입력받은 순서대로, 오른쪽 스텍에는 반대로 넣어주면 된다. 스택으로 구현하게 되면 문자열의 최대길이가 N+M이면 시간 복잡도는 O(M+N)이 된다.

또한 이는 링크드 리스트로도 구현이 가능하다. 링크드 리스트는 특정 위치에 삽입/삭제를 할 때 유용한 DS다!

 

알고리즘 구현은 쉬웠는데 cin이랑 scanf 오류때매 오래걸렸다....하...

찾아보니까 cin이 scanf에 비해 컴퓨터가 알아서 처리해야할게 많아서 성능이 차이난다고 하는데 그 문제가 아니었다!!! scanf로 했을 때는 cmd를 입력하지 않았는데 그냥 혼자서 빈 문자열을 인식하고 P 명령어를 입력하면 c를 입력 못받고 그랬는데 cin으로 싹 바꾸니까 바로 해결됨 뭐지 진짜????? 쒸익쒸익

흠 찾아보니까 scanf는 \n을 만날때까지 입력을 받기 때문에 \n은 계속 입력버퍼에 남아있게 된다고 한다. 이를 해결하려면 다음 scanf에서 "% c"와 같이 앞에 공백을 두고 받아야한다고 한다. 그래서 예제 코드에도 공백이 있었나봉가? 암튼 난 cin으로 해결하였따!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

#include <iostream> #include <string> #include <stack> #include <stdio.h> #include <cstdio> #include <cstring> using namespace std; int main(void) {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     string str;     cin >> str;          stack<char> left, right;          for (int i = 0; i < str.length(); i++)     {         left.push(str[i]);     }     int n;     cin >> n;       while(n--)     {         char cmd;         cin >> cmd;                  if (cmd == 'L')         {             if (!left.empty())             {                 right.push(left.top());                 left.pop();             }         }         else if (cmd == 'D')         {             if (!right.empty())             {                 left.push(right.top());                 right.pop();             }         }         else if (cmd == 'B')         {             if (!left.empty())             {                 left.pop();             }         }         else if (cmd == 'P')         {             char c;             cin >> c;             left.push(c);         }     }     while (!left.empty())     {         right.push(left.top());         left.pop();     }     while (!right.empty())     {         cout << right.top();         right.pop();     }     printf("\n");     return 0; }

cs

 

스택 강의 끝!! 다음 강의는 큐지롱~