[민코딩] 훈련반2 1주차

• 파싱
  • 문자열에서 원하는 문자만 뽑아내는 것
  • 필요한 이유
    • 현업에서 많이 사용
    • 코테에서 자주 등장
    • 디버깅 훈련

• <cstring>: c의 <string.h>
  • strcmp
  • strcpy

• c와 c++은 문자열 사용이 매우 불편하다
  • char 배열을 사용해야 한다
  • 복사와 비교가 어렵다
  • int형처럼 사용할 수 없다

• <string>: c++의 stirng 클래스
  • int형처럼 사용 가능하다
    • 복사와 비교를 쉽게 할 수 있다
  • 문자열처럼 사용 가능하다
    • char ch = str[0] // OK
  • .length()
    • .size()와 같다
    • 문자열 길이

string str = "BBQ";

// 비교
str = "WER"
if(str=="WER") cout<<"같다";

// 복사
string str2 = str;

• strlen은 for문 선언문 내에서 사용하지 않는 것이 좋다
  • 이미 strlen 내부에 for문이 작동하기 때문
  • .length()는 for문 선언문 내에서 사용해도 ok

• class
  • C에서는 struct 내부에 함수 정의 불가능
  • C++에서는 struct 내부에 함수 정의 가능
    • class와 struct가 유사한 개념
  • .length(): 메서드의 일종
  • 자동으로 문자열이 초기화되기 때문에 선언 시, 값을 넣어줄 필요가 없다

• .find()
  • 특정 문자열 내부에서 지정한 문자열의 첫 번째 인덱스를 반환하는 메서드
  • 찾으려는 문자열이 없으면 -1 반환
  • .find("찾을 문자열", 지정 인덱스)
    • 지정 인덱스부터 문자열을 찾는다
  • visualization
    • 반도체 회사: 로그 데이터 출력

string str = "BOPEJFSKFCOEPJ";
int idx = str.find("KFC"); // 7

• 문자열 덧셈

string a = "ABC";
string b = "BDS";
string c = a + b;

string d = a + "CBD"; // OK (string class + 문자열)
string e = "ADE" + "CDE"; // NO (문자열+문자열)

string e = "ADE";
e+="CDE"; // OK

string e = string("ADE") + string("CDE"); // OK

• substr(시작 인덱스, 글자 수)
  • 시작 인덱스부터 글자 수만큼 글자 추출

string str = "ejpfjspes";
string sstr = str.substr(2, 4); // pfjs

• A~Z까지 문자열 만들기

string str;
    
for (char i = 'A'; i <= 'Z'; i++)
{
   str += i;
}

• C언어 문자열을 C++ string으로 바꾸기

char buf[10] = "soejpse";
string str = buf;

• C++ string을 C언어 문자열로 바꾸기

strcpy(buf, str.c_str());
printf("%s", str.c_str());

• stoi()
  • 문자열을 정수형으로 바꾸기

string str = "1234";
int i = stoi(str);

• to_string()
  • 정수형을 문자열로 바꾸기

int n = 1234;
string s = to_string(n);

---

• split 메서드
  • c++에는 split 메서드가 없다
  • substr과 find로 구현 가능하다
  • 직접 구현

void split(string result[], int& rn, string str, string tar)
{
    str += tar;
  
    int a = 0;
    int b = 0;
  
    while(1){
        b = str.find(tar, a);
        if(b == -1) break;
    
        string temp = str.substr(a, b - a);
        result[rn++] = temp;
    
        a = b + 1;
    } 
}

• erase()
  • 첫번째 인자는 시작 인덱스, 두번째 인자는 글자 수
  • 시작 인덱스부터 글자 수만큼 글자를 지우는 메서드

• insert()
  • 첫번째 인자는 목표 인덱스, 두번째 인자는 삽입할 문자열
  • 목표 인덱스에 삽입할 문자열을 넣는 메서드

• replace 메서드
  • c++에는 replace 메서드가 없다
  • find와 erase, insert로 구현 가능하다
  • 직접 구현

string str = "ABKFC_KFC";

int a = 0;
int b = 0;

while (1)
{
    b = str.find("KFC", a);
    if (b == -1) break;
    str.erase(b, b - a + 1);
    str.insert(b, "***");
    a = b + 1;
}

• 유효성 검사(Vaild Check)
  • 파싱 전 유효한 문자열인지 검사하는 것
  • ex:) 비밀번호 - 특수문자, 영어 대소문자, 숫자
  • 조건이 많으므로 flag보다는 isVaild 함수로 빼는 것이 낫다

---

• 구조체 배열

struct S
{
    int a;
    int b;
};

S s[4] = { {3,7},{4,2},{6,5},{1,3} };

• 구조체 포인터

struct BTS
{
    int a;
    int b;
};

BTS x;
BTS* p = &x;
BTS* g = &x;

(*p).a = 3;
(*p).b = 4;

cout << (*g).a << " " << (*g).b;

• g->a
  • (*g).a와 같은 의미
  • 구조체 포인터 g가 가리키는 곳 안에 있는 a

• 가짜 Linked List

struct Node
{
    int x;
    Node* p;
};

Node* h = &a;
Node a, b;

a.p = &b;

h->x = 7;
h->p->x = 15;

• g = g->p
  • 포인터 g를 오른쪽 노드로 옮기는 코드
  • p가 다음 노드의 주소를 가지고 g 변수에 복사되어 g가 다음 노드를 가리키게 된다

• 노드 탐색

Node* g = h;

// WHILE문
while(g != NULL){
    cout << g -> x;
    g = g -> p;
}

// FOR문
for(Node *g = h; g != NULL; g = g->p)
{
    cout << g -> x;
}

• HEAP
  • 지역 변수가 저장되는 STACK에서는 동적 할당 불가능
  • new int()를 통해 STACK 대신 HEAP에 변수를 저장함으로써 동적 할당이 가능해진다
  • new int()는 주소를 가지므로 포인터 변수에 저장한다
  • 이때, 포인터 변수는 STACK에 저장된다

int* p = new int[5];

*(p + 0) = 100;
*(p + 1) = 101;
*(p + 2) = 102;
*(p + 3) = 103;
*(p + 4) = 104;

int n;
cin >> n;

// 원하는 만큼 값 할당 가능
int* p = new int[n];

for(int i=0;i<n;i++)
{
    p[i] = i;
}

• 링크드 리스트 구현

struct Node
{
    int x;
    Node* p;
};

Node* head = NULL;
Node* last = NULL;

void AddNode(int n)
{
    if (head == NULL)
    {
        head = new Node();
        head->x = n;
        last = head; // head와 같은 곳을 가리킴
    }
    else
    {
        last->p = new Node();
        last = last->p;
        last->x = n;
    }
}

int main()
{
    AddNode(1);
    AddNode(3);
    AddNode(5);
    AddNode(7);

    // 노드 탐색
    for (Node* g = head; g != NULL; g = g->p)
    {
        cout << g->x<<" "; // 1 3 5 7
    }

}

• stl 링크드 리스트 라이브러리
  • 위에 구현한 링크드 리스트와 동일한 기능

#include<iostream>
#include<list>
using namespace std;

list<int> h;

int main()
{
    h.push_back(1);
    h.push_back(2);
    h.push_back(3);

    for (auto i = h.begin(); i != h.end(); ++i)
    {
        cout << *i;
    }
}

---

• vector
  • 배열의 상위 버전
    • 배열에 비해 삽입, 삭제가 자유롭다
  • #include<vector>
  • .size()
    • vector의 크기를 알려주는 메서드
  • .push_back()
    • vector의 마지막에 새로운 원소를 추가하는 메서드
  • .pop_back()
    • vector의 마지막 원소부터 차례대로 제거하는 메서드
    • 정의된 vector의 크기를 고려하여 사용해야 한다

vector<int> v = { 1,5,7,9 };

v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4); // { 1,5,7,9,1,2,3,4 }

v.pop_back(); // { 1,5,7,9,1,2,3 }

• ctrl+f5 런타임 에러 발생
  • 자세히 알 수 없으니 일단 끄고 다시 f5 누른 후 무시 누르기
  • 어느 부분에서 오류가 났는지를 알려준다

• vector 크기 지정

vector<int> v(3); // 세 칸 만들기
vector<int> a(3, 10); // 세 칸의 vector를 전부 10으로 초기화

v[2] = 15;

• string vector
  • string으로 구성된 1차원 배열

string str = "ABC";
cout << str[0];

vector<string> v = { "ABC", "BTS" };
cout << v[0][1]; // B

vector<string> str;

for(int i=0;i<4;i++)
{
    string temp;
    cin>>temp;
    v.push_back(temp);
}

• Vector 탐색 방법
  • auto
    • 자동으로 타입 셋팅
  • iterator 포인터의 이동

// vector에서 가능한 탐색 방법 = 배열 탐색 방법
for(int i=0;i<q.size();i++){
    cout<<q[i];
}

// STL 공용으로 쓰는 탐색 방법
for(auto i=q.begin(); i!=q.end(); ++i){
    cout<<*i; // vector의 시작부터 끝까지 포인터 옮김
}

• iterator
  • 간단히 auto로 바꿔 쓴다

vector<int>::iterator i
i=q.begin(); // 첫번째 노드
i++;
i=q.end(); // 마지막 노드의 다음 칸

• 배열과 다르게 함수의 인자 혹은 반환값으로 사용 가능하다

vector<int> bts(vector<int> a){
    return {9,9,8};
}

int main(){
   vector<int> a = {1,2,3,4,5};
   vector<int> ret = bts(a); // {9,9,8}
}

• 레퍼런스
  • 포인터 대용
  • &변수명
  • 별명
  • swap 함수의 원리

void bts(int& hp){
    hp = 200;
}

int main(){
    int energy = 500;
    bts(energy); // 200
}

• vector 속 vector
  • 이차원 배열과 유사한 개념

vector<vector<int>> v;

v.push_back({ 1,3,2 });
v.push_back({ 5,4 });
v.push_back({ 1,2,3,4 });
v.push_back({ 5 });

for (int y = 0; y < v.size(); y++)
{
    for (int x = 0; x < v[y].size(); x++)
    {
        cout << v[y][x] << " ";
    }
    cout << '\n';
}

// 초기화가 자유롭다
vector<vector<int>> vect;

for (int i = 0; i < 4; i++)
{
    vect.push_back({ 0,0,1,0 });
    vect.push_back({ 0,2,3,0 });
    vect.push_back({ 0,0,0,4 });
    vect.push_back({ 5,0,0,0 });

}

• 그래프
  • 노드의 값과 노드 간 관계를 함께 담고 있는 자료구조
  • for문으로 탐색하기 어렵다
    • DFS, BFS 활용

• 그래프 초기화
  • 배열 두 개가 필요함(인접 행렬)
    • 관계를 저장하는 이차원 배열
    • 값을 저장하는 일차원 배열
  • 인덱스를 사용자 마음대로 정할 수 있다