[코테] 코테 공부 시작 전 준비 (2)

타입 캐스팅

• 문자열
  string ~> int

  int x = 100;
  string new_str = to_string(x);

• 문자열의 인덱스 하나씩 비교할 때
  문자열의 각 인덱스는 char 타입이 된다. 만약 그 값을 직접 이용하려고 할 때, char는 ASCII Code에 해당하는 정수 값으로 대체된다.
  '0' 이전은 '/', '9' 이후는 ':'라는 걸 알아두면 편할 듯!
  

• 정수
  int ~> string

  string x = "100";
  int new_int = stoi(x);

자료구조

동적 할당

• 배열

  • new, delete

  int size;
  cin >> size;
  int* new_array = new int[size]();  // 배열을 생성하면서, 값들을 0으로 초기화
  
  vector<int>* adj_list = new vector<int>[size+1];
  
  delete[] new_array;
  delete[] adj_list;
  

큐

• FIFO (First In, First Out)

• .push(data) : 큐에 data 삽입

• .pop() : 큐에서 제일 앞에 있는 데이터 제거

• .empty() : 큐가 비어있는 지 확인

• .front() : 큐 제일 앞의 객체 리턴

• .back() : 큐 제일 뒤의 객체 리턴

  #include <iostream>
  #include <queue>
  
  using namespace std;
  
  int main() {
      queue<int> q;   // int형 큐
  
      q.push(7);
      q.push(10);
      q.push(5);
      q.pop();
      q.push(3);
  
      while(!q.empty()) {
          cout << q.front() << " ";
          q.pop();
      }
  
      cout << endl;
  
      return 0;
  }

스택

• LIFO (Last In, First Out)

• .push(data) : 스택에 data 삽입

• .pop() : 스택에서 제일 위에 있는 데이터 제거

• .empty() : 스택이 비어있는 지 확인

• .top() : 스택 제일 위의 객체 리턴

• .back() : 스택 제일 아래의 객체 리턴

  #include <iostream>
  #include <stack>
  #include <queue>
  
  using namespace std;
  
  int main() {
      stack<int> s;
  
      s.push(7);
      s.push(10);
      s.push(5);
      s.pop();
      s.push(8);
  
      while (!s.empty()) {
          cout << s.top() << " ";
          s.pop();
      }
  
      cout << endl;
  
      return 0;
  }

그래프

• 구조체를 이용

  #include <iostream>
  
  using namespace std;
  
  typedef struct Graph {
      int visited;
      int node_num;
      Graph* next;
  } Graph;
  
  Graph* NewGraph(int);
  void PrintGraph(Graph*);
  
  int main() {
      Graph* g1 = NewGraph(1);
      Graph* g2 = NewGraph(2);
      Graph* g3 = NewGraph(3);
      Graph* g4 = NewGraph(4);
      Graph* g5 = NewGraph(5);
      Graph* g6 = NewGraph(6);
      Graph* g7 = NewGraph(7);
  
      // 인접리스트
      int adj_list[7];
  
      g1->next = g2;
      g2->next = g3;
      g3->next = g4;
      g4->next = g5;
      g5->next = g6;
      g6->next = g7;
      PrintGraph(g1);
  
      delete g1;
      delete g2;
      delete g3;
      delete g4;
      delete g5;
      delete g6;
      delete g7;
  }
  
  Graph* NewGraph(int n) {
      Graph* new_graph = new Graph;
      new_graph->visited = 0;
      new_graph->next = NULL;
      new_graph->node_num = n;
  
      return new_graph;
  }
  
  void PrintGraph(Graph* node) {
      if (node == NULL) {
          return;
      }
      else {
          cout << node->node_num << endl;
          PrintGraph(node->next);
      }
  }

• vector를 이용

  • vector<int> : 벡터의 타입 선언
  • .push_back(data) : 해당 벡터의 인접 리스트에 data를 추가

  #include <iostream>
  #include <vector>
  
  using namespace std;
  
  vector<int>* A;
  int* visited;
  
  void dfs(int n) {
      if (visited[n] == 1) {
          return;
      }
      else {
          cout << n << " ";
          visited[n] = 1;
          for (int i=0; i<A[n].size(); i++) {
              if (visited[A[n][i]] == 0) {
                  dfs(A[n][i]);
              }
          }
      }
  }
  
  int main() {
      int size = 6;
  
      A = new vector<int>[size+1];
      visited = new int[size+1]();
  
      A[1].push_back(2);
      A[1].push_back(5);
      A[2].push_back(1);
      A[2].push_back(4);
      A[2].push_back(5);
      A[3].push_back(2);
      A[3].push_back(4);
      A[4].push_back(2);
      A[4].push_back(3);
      A[4].push_back(5);
      A[4].push_back(6);
      A[5].push_back(1);
      A[5].push_back(2);
      A[5].push_back(4);
      A[6].push_back(4);
  
      dfs(1);
  
      delete[] A;
      delete[] visited;
  }

트리

• 구조체를 이용

  • root 를 전역변수로 선언하여 활용
  • root를 함수 인자로 주고받아 활용

  #include <iostream>
  #include <queue>
  
  using namespace std;
  
  struct Node {
      int data;
      Node* left;
      Node* right;
  };
  
  // 새 노드 생성
  Node* NewNode(int _data) {
      Node* tmp = new Node;
      tmp->data = _data;
      tmp->left = NULL;
      tmp->right = NULL;
  
      return tmp;
  }
  
  // 노드 삽입 (트리)
  Node* InsertNode(Node* root, int _data) {
  
      queue<Node*> q;
      q.push(root);
  
      while (!q.empty()) {
          Node* tmp = q.front();
          q.pop();
  
          if (tmp->left != NULL) {
              q.push(tmp->left);
          }
          else {
              tmp->left = NewNode(_data);
              return root;
          }
          if (tmp->right != NULL) {
              q.push(tmp->right);
          }
          else {
              tmp->right = NewNode(_data);
              return root;
          }
      }
  }
  
  void preorder(Node* root) {
      if (root == NULL) return;
      cout << root->data << "->";
      preorder(root->left);
      preorder(root->right);
  }
  
  void inorder(Node* root) {
      if (root == NULL) return;
      preorder(root->left);
      cout << root->data << "->";
      preorder(root->right);
  }
  
  void postorder(Node* root) {
      if (root == NULL) return;
      preorder(root->left);
      preorder(root->right);
      cout << root->data << "->";
  }
  
  int main() {
      Node* root = NewNode(1);
      root = InsertNode(root, 2);
      root = InsertNode(root, 3);
      root = InsertNode(root, 4);
      root = InsertNode(root, 5);
      root = InsertNode(root, 6);
      root = InsertNode(root, 7);
  
      preorder(root);
      cout << endl;
      inorder(root);
      cout << endl;
      postorder(root);
      cout << endl;
  
      delete[] root;
  
      return 0;
  }