[바킹독의 실전 알고리즘] 0x05 스택 복습 -C++

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여,

필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다.

(이것은 다 ~ 개강 전까지 그동안 굳어있던 머리를 활성화 시키기 위한 발악인 것입니다...)

바킹독의 실전 알고리즘 0x05강 링크

 

강의내용 복습

스택의 정의와 성질

스택 : 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조, LIFO(Last In First Out)

*Restricted Structure : 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있음(스택, 큐, 덱)

 

스택의 성질

1. 원소의 추가가 O(1)

2. 원소의 제거가 O(1)

3. 제일 상단의 원소 확인이 O(1)

4. 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가

     (스택에서 제공하는 기능이 아님)

 

스택의 기능과 구현

배열이나 연결리스트를 이용해서 구현하는데, 배열로 구현하는 것이 더 쉽다.

const int MX = 1000005;
int dat[MX]; //원소를 담을 큰 배열
int pos = 0; //인덱스를 저장할 변수, 다음에 원소가 추가될 때 삽입해야 하는 위치, 원소의 수를 의미

#include <bits/stdc++.h>
using namespace std;
 
const int MX = 1000005;
int dat[MX];
int pos = 0;
 
void push(int x){
    dat[pos++] = x;
}
 
void pop(){
    pos--;
}
 
int top(){
    return dat[pos-1];
}
 
void test(){
  push(5); push(4); push(3);
  cout << top() << '\n'; // 3
  pop(); pop();
  cout << top() << '\n'; // 5
  push(10); push(12);
  cout << top() << '\n'; // 12
  pop();
  cout << top() << '\n'; // 10
}
 
int main(void) {
	test();
}

 

STL stack

STL stack을 쓰면, 만약 코드가 오류났을 경우 최소 스택쪽에서는 문제가 없다는 것을 알 수 있으니 로직을 바로잡기에 편하다. STL stack을 사용하기 위해서는 #include <stack>을 포함해야한다.

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
  stack<int> S;
  S.push(10); // 10, 스택에 10 추가
  S.push(20); // 10 20
  S.push(30); // 10 20 30
  cout << S.size() << '\n'; // 3, 스택의 현재 사이즈 반환
  if(S.empty()) cout << "S is empty\n"; //스택이 비어있으면 true를, 아니면 false 반환
  else cout << "S is not empty\n"; // S is not empty
  S.pop(); // 10 20
  cout << S.top() << '\n'; // 20
  S.pop(); // 10
  cout << S.top() << '\n'; // 10
  S.pop(); // empty
  if(S.empty()) cout << "S is empty\n"; // S is empty
  cout << S.top() << '\n'; // 스택이 비어있는 경우에 top또는 pop을 호출하면 runtime error 발생
}

코드를 제출했을때 runtime error가 발생했다면, 스택이 비어있는데 top이나 pop을 했는지 의심해볼 수 있다.

 

연습문제 복습(C++)

강의 후반부 및 아래 링크로 들어가면 나오는 문제들 중 해당 강의에 맞는 연습문제들을 풀고

정답코드와 비교하며 얻은 내용들을 간단히 정리한 내용입니다.

연습문제 링크

 

string 문자열 확장하는 법

1. += 연산자 이용

string ans;
ans += "+\n";
int num = 3456;
ans += to_string(num);

2. append() 이용

string ans;
ans.append("+\n");
int num 3456;
ans.append(to_string(num));

 

pair <type1, type2> p;

#include <utility> / #include <vector> / #include <algorithm> 

first : 첫번째 인자를 반환

second : 두번째 인자를 반환

stack<pair<int, int>> S;
S.push({10, 2});
cout << S.top().first << "\n"; //10 출력
cout << S.top().second << "\n"; //2 출력
 
pair<int, int> P;
P = make_pair(6, 3); //P = {6, 3};와 동일(C++11이상)
cout << P.first << "\n"; //6 출력
cout << P.second << "\n"; //3 출력

 

monotone stack : 스택 내의 원소들을 오름차순/내림차순으로 유지하는 아이디어

 

 

 

 

 

*다풀었다 !!!