• 문제풀이함.
  • 새로운 문자열을 얻을 때, for문 돌면서 마지막 문자열 처리를 안해줘서 약간 헤멤
  • 로직을 손으로 정확히 안짜봤기 때문에 발생한 문제인것 같기도 함.

#include <vector>
#include <iostream>
#include <queue>

#define MAX_SIZE 10

using namespace std;

vector<vector<int>> maze = {
    {1,0,1,1,1,1},
    {1,0,1,0,1,0},
    {1,0,1,1,1,1},
    {1,1,1,0,1,1},
};

int numOfX = 6;
int numOfY = 4;

pair<int, int> startPos = { 0, 0 };
pair<int, int> endPos = { 5, 3 };

bool isVisit[MAX_SIZE][MAX_SIZE];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

vector<pair<int, int>> path;

bool isValidXY(int x, int y)
{
    if ((x < 0) || (y < 0) || (x >= numOfX) || (y >= numOfY))
        return false;
    return true;
}

void dfs(int x, int y)
{
    // 진입시 바로 할 일
    isVisit[x][y] = true;
    path.push_back({x, y});

    // 종료조건 + 종료시 처리할 것 goto
    if ((x == endPos.first) && (y == endPos.second)) {
        for (int i = 0; i < path.size(); i++) {
            cout << "[" <<path[i].first << "," << path[i].second << "]";
        }
        cout << endl;
        goto exit;
    }

    // 다음 노드 진입 및 가지치기
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        // vector<vector<int>> 의 경우 x,y가 아닌 y, x 순으로 접근 필요
        if (isValidXY(nx, ny) && (maze[ny][nx] == 1) && (isVisit[nx][ny] == false)) {
            dfs(nx, ny);
        }
    }

    // 종료시 처리할  것
exit:
    isVisit[x][y] = false;
    path.pop_back();
}

struct Pos {
    int x, y;
    int level;
};

void bfs(int x, int y)
{
    queue<Pos> q;
    q.push({ x, y, 1});
    // 진입시 바로 할 일
    isVisit[x][y] = true;

    while (!q.empty()) {
        Pos curPos = q.front();
        q.pop();

        // 종료조건
        if ((curPos.x == endPos.first) && (curPos.y == endPos.second)) {
            cout << curPos.level << endl;
            break;
        }

        // 다음 노드 진입 및 가지치기
        for (int i = 0; i < 4; i++) {
            int nx = curPos.x + dx[i];
            int ny = curPos.y + dy[i];
            // vector<vector<int>> 의 경우 x,y가 아닌 y, x 순으로 접근 필요
            if (isValidXY(nx, ny) && (maze[ny][nx] == 1) && (isVisit[nx][ny] == false)) {
                q.push({nx, ny, curPos.level + 1});
                // 집입시 바로 할 일
                isVisit[nx][ny] = true;
            }
        }
    }
}

int main()
{
    //dfs(0, 0);
    //bfs(0, 0);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

vector<char> elements = { 'A', 'B', 'C', 'D' };
vector<char> path;

void dfs(int preIdx)
{
    // print path
    if (path.size() != 0) { // not include anything yet
        cout << path.size() << " : ";
        for (int i = 0; i < path.size(); i++) {
            cout << path[i] << " ";
        }
        cout << endl;
    }

    for (int i = preIdx + 1; i < elements.size(); i++) {
        path.push_back(elements[i]);
        dfs(i);
        path.pop_back();
    }
}

int main()
{
    dfs(-1);
    return 0;
}

1. Groups and ranges (그룹과 범위)

   • | : 또는
   • () : 그룹 - 찾은 것을 그룹별로 알려줌
     • (?:) : 찾긴하지만 그룹으로 기억하지는 않음
   • [] : 문자셋, 괄호안의 어떤 문자든 - (||)과 비슷한 효과
     • 예) [a-f0-9] : a부터 f까지 혹은 0부터 9까지 찾은
   • [^] : 제외

      - 예) [^a-f0-9] : a부터 f까지 혹은 0부터 9까지를 제외하고 찾음

2. Quantifiers (수량)

   • ? : zero or one
   • • : zero or more
   • • : one or more
   • {n} : n번 반복
   • {min,} : 최소
   • {min, max} : 최소, 최대

3. Boundary

   • \b : 단어 경계
     • 예) \bYa 로 찾으면 YaYaYa 중 앞에 있는 YaYaYa로 검색
     • 예) Ya\b로 찾으면 YaYaYa 중 뒤에 있는 YaYaYa로 검색
       • Ya 하나만을 놓고보면 둘다 경계이기 때문에 Ya 검색됨
   • \B : 단어 경계가 아님
     • 예) \BYa 로 찾으면 YaYaYa 중 YaYaYa로 검색
     • 예) Ya\B로 찾으면 YaYaYa 중 뒤에 있는 YaYaYa로 검색
       • Ya 하나만을 놓고보면 둘다 경계이기 때문에 검색되지 않음
   • ^ : 문장의 시작
     • 예) ^Ya로 찾으면 Ya ya YaYaYa Ya 중 Ya ya YaYaYa Ya 로 검색
   • $ : 문장의 끝 (플래그에 multiline이 안되어 있으면... 전체문장중에만 찾음)
     • 예) $Ya로 찾으면 Ya ya YaYaYa Ya 중 Ya ya YaYaYa Ya 로 검색

4. Character classes

   • . : 모든 문자 (새로운줄바꿈 문자 제외)
   • \ : 특수문자가 아닌 문자
     • . : 문자 . 검색
     • ? : 문자 ? 검색
     • [ : 문자 [ 검색
   • \d : 숫자(digit)
   • \D : 숫자가 아닌 모든문자
   • \w : 숫자를 포함한 모든문자(word) - 특수문자, 공백 제외
   • \W : 숫자를 포함한 모든문자를 제외한 특수문자, 공백 등
   • \s : 공백(space)
   • \S : 공백을 제외한 나머지

주의

• C++에서 \d를 하니깐... digit 검색이 되지 않았다.. \d를 사용해야한다.

퍼옴

Notice that, in C++, character and string literals also escape characters using the backslash character (\), and this affects the syntax for constructing regular expressions from such types. For example:
1 std::regex e1 ("\\d");  // regular expression: \d -> matches a digit character
2 std::regex e2 ("\\\\"); // regular expression: \\ -> matches a single backslash (\) character 

c++에서 string에서 \는 escape 로 사용되기 때문에... \를 사용하기 위해서는 \로 써야한다.

• 예1) \d : \d : 숫자
• 예2) \\ : \ : 문자 \
• [] 안에서는 특수문자 바꿔줄 필요는 없어보임
  • 밖에서 \.을 써야 문자 . 을 나타내지만, [.] 문자셋 안에서는 .으로 써도 되는듯
  • regex reg("[.]{3}"); 하니까 "..."이 검색됨!

연습

#include <iostream>
#include <string>
#include <regex>

using namespace std;

vector<string> getMatches(string str, regex reg)
{
    vector<string> matches;

    // sregex_iterator 내, begin(), end(), reg를 저장하여 순회 가능
    sregex_iterator curMatch(str.begin(), str.end(), reg);
    // lastMatch는 end로 초기화됨
    sregex_iterator lastMatch;

    while (curMatch != lastMatch) {
        smatch match = *curMatch;
        matches.push_back(match.str());
        curMatch++;
    }

    // match.str() // match된 string
    // match.prefix() // match된 string 앞 부분
    // match.suffix() // match된 string 뒷 부분

    return matches;
}

vector<string> getCaptures(string str, regex reg)
{
    vector<string> matches;

    // sregex_iterator 내, begin(), end(), reg를 저장하여 순회 가능
    sregex_iterator curMatch(str.begin(), str.end(), reg);
    // lastMatch는 end로 초기화됨
    sregex_iterator lastMatch;

    while (curMatch != lastMatch) {
        smatch match = *curMatch;
        matches.push_back(match[1]);
        curMatch++;
    }

    // match.str() // match된 string
    // match.prefix() // match된 string 앞 부분
    // match.suffix() // match된 string 뒷 부분

    return matches;
}

int main()
{
    string str = "\
Hi there, Nice to meet you. And Hello there and hi.\n\
I love grey(gray) color not a gry, graayand graaay.grdy\n\
Ya ya YaYaYa Ya\n\
abcdefghijklmnopqrstuvwxyz\n\
ABSCEFGHIJKLMNOPQRSTUVWZYZ\n\
1234567890\n\
.[]{}()\^$|?*+\n\
010-898-0893\n\
010 898 0893\n\
010.898.0893\n\
010-405-3412\n\
02-878-8888\n\
dream.coder.ellie@gmail.com\n\
hel+lo@daum.net\n\
hello@daum.co.kr\n\
...\n\
http://www.youtu.be/-ZClicWm0zM\n\
https://www.youtu.be/-ZClicWm1zM\n\
https://youtu.be/-ZClicWm2zM\n\
youtu.be/-ZClicWm3zM";

    regex reg1("\\d{2,3}[- .]\\d{3}[- .]\\d{4}"); // 전화번호 검색
    regex reg2("[\\w+-._]+@[\\w+-._]+"); // 이메일 검색
    regex reg3("(?:https?:\\/\\/)?(?:www\\.)?youtu\\.be\/([a-zA-Z0-9-]+)"); // 유튜브에서 ID만 가져오기...

    //vector<string> matches = getMatches(str, reg3);
    vector<string> matches = getCaptures(str, reg3);

    for (int i = 0; i < matches.size(); i++) {
        cout << i << " : " << matches[i] << endl;
    }
    return 0;
}

• visual studio 디버깅 모드 한 번 미리 실행할 것! (로딩시간이 걸림)
• 최적화 문제는 일단 먼저 최적화 없이 구현한 후, 시간될 때 최적화 한다.
• 정확하게 문제 읽고! 정확하게 이해하고! 알고리즘 정확하게 생각한 뒤! 코드 구현.
• 큰 흐름부터 먼저 다 짜고, 세부 흐름을 완성시킨다! (복잡할 수록 코드 구현시 효과가 좋음)
• 조급할 것 없음. 내가 어려우면 남도 어려움.
• 인덱스를 문제와 일치시키면, 디버깅시 직관적 해석이 가능하니 일치여부 고민필요!
• 전역변수 초기화 필요한지 체크하기!

대략적인 1초 계산방법

• O(N) : 1000만
• O(NlogN) : 10만
• O(N^2) : 2000
• O(N^3) : 500

자료구조

vector

• 위치 접근 : O(1)
• 뒤에 원소 추가/제거 : O(1) - push_back, pop_back
• 임의 위치 원소 추가/제거 : O(N) - insert, erase
• 꽉 찬 상태에서 원소 추가시, 새로운 공간 할당 및 복사가 이루어짐.

#include <vector>

using namespace std;

int main()
{
    vector<int> vec;

    vec.push_back(10); // 맨 뒤에 10 추가
    vec.pop_back();    // 맨 뒤에 제거
    vec.size(); // 원소 개수
    vec.capacity(); // 여분 포함 - 그때 그때 다름
    vec.insert(vec.begin(), 100); // iter 자리에 100 삽입
    vec.erase(vec.begin());       // iter 자리 삭제
    vec[0]; // index를 통한 접근
    vec.begin(); vec.end(); // 주의 : capacity 만큼 iterator가 동작하므로, size와 다르게 쓰레기값이 있을 수 있음

    return 0;
}

list

• 임의의 위치 추가/제거 : O(1), 위치를 찾는데 O(N)
• cache hit율이 떨어짐

#include <iostream>
#include <list>

using namespace std;

int main()
{
    list<int> li;

    li.insert(li.end(), 3); // 마지막 원소 추가
    li.insert(li.begin(), 5); // 처음 원소 추가
    li.remove(3); // 3 원소 제거
    li.erase(li.begin()); // iter를 사용한 삭제

    // iter 접근
    for (list<int>::iterator iter = li.begin(); iter != li.end(); ++iter)
    {
        cout << *iter << " - ";
    }
    cout << endl;

    return 0;
}

deque

• vector와 비슷하나 앞, 뒤 추가/삭제 : O(1)
• 원소들이 메모리상에서 연속적으로 존재하지 않음
• 꽉 찬 상태에서 원소 추가시, vector와 달리 기존의 원소를 복사하지 않음

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque<int> dq;

    dq.push_front(40); // 앞에 원소 추가
    dq.push_back(10); // 뒤에 원소 추가
    dq.front(); // 앞 원소 확인
    dq.back(); // 뒤 원소 확인
    dq.pop_front(); // 앞 원소 제거
    dq.pop_back(); // 뒤 원소 제거

    for (deque<int>::iterator iter = dq.begin(); iter != dq.end(); iter++)
    {
        cout << *iter << " - ";
    }
    cout << endl;

    return 0;
}

map

• 균형 이진 트리 구조
• key, value 쌍
• key는 고유한 값으로 중복이 불가능함
• 삽입이 되면서 자동으로 정렬됨 (default는 오름차순)

#include <map>
#include <iostream>

using namespace std;

int main()
{
    map<string, int> m;

    m["kh"] = 34;
    m["sm"] = 31;
    m["bm"] = 32;

    cout << m["kh"] << endl;
    cout << m["sm"] << endl;
    cout << m["bm"] << endl;

    auto it = m.find("ks");
    if (it == m.end()) {
        cout << "Not Exist" << endl;
    }
    else {
        cout << "Exist" << endl;
    }

    return 0;
}

priority_queue, heap

#include <queue>
#include <iostream>

using namespace std;

struct Data {
    string name;
    int age;
};

// age 기준 min heap
struct compare {
    bool operator()(Data a, Data b) {
        if (a.age > b.age)
            return true;
        return false;
    }
};

int main()
{
    // min heap
    priority_queue<int, vector<int>, greater<int>> heap;
    // max heap
    //priority_queue<int, vector<int>, less<int>> heap;

    heap.push(3);
    heap.push(1);
    heap.push(2);

    while (heap.empty() == false) {
        int top = heap.top();
        cout << top << endl;
        heap.pop();
    }

    // struct, custom heap
    priority_queue<Data, vector<Data>, compare> customHeap;
    customHeap.push({ "kh", 34 });
    customHeap.push({ "sm", 31 });
    customHeap.push({ "bm", 32 });

    while (customHeap.empty() == false) {
        Data top = customHeap.top();
        cout << top.name << " : " << top.age << endl;
        customHeap.pop();
    }

    return 0;
}

string

기본 string 동작

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string str = "Hello";
    string str2 = "String2";
    char arr[20];

    str.push_back('!');           // "Hello!"
    str.pop_back();               // "Hello"
    str = str + "!!!";            // "Hello!!!"
    str[0];                       // 'H'
    str.length();                 // 8
    str.c_str();                  // "Hello!!!" // c 스타일의 배열 문자열로 변환
    str.substr(2, 4);             // "ello!" // 2번째 부터 length 4 slice
    str.replace(5, 3, ", World"); // "Hello, World" // 5번째부터 length 2개 제거 후, 내용 삽입
    str.compare("Hello, World");  // 같으면 0, ==
    str.find("Hello");            // 찾으면 0
    str.copy(arr, 4, 1);          // arr : ello // length 4, index 1 를 arr에 복사
    str.begin();                  // 시작 iterator
    str.end();                    // 끝 iterator (개방)
    swap(str, str2);              // reference 교환 스왑

    // 대문자 변환 , 소문자는 tolower 사용
    for (int i = 0; i < str.length(); i++)
    {
        str[i] = toupper(str[i]);
    }

    return 0;
}

split string

#include <sstream>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<string> split(string input, char delimiter) {
    vector<string> strs;
    stringstream ss(input);
    string line;

    while (getline(ss, line, delimiter)) {
        strs.push_back(line);
    }

    return strs;
}

int main()
{
    string str = "This is example";
    vector<string> strs = split(str, ' ');

    for (int i = 0; i < strs.size(); i++) {
        cout << strs[i] << endl;
    }

    return 0;
}

regex, 정규표현식

#include <iostream>
#include <regex>
#include <vector>
#include <string>

using namespace std;

vector<string> getMatches(string str, regex reg)
{
    vector<string> matches;

    // sregex_iterator 내, begin(), end(), reg를 저장하여 순회 가능
    sregex_iterator curMatch(str.begin(), str.end(), reg);
    // lastMatch는 end로 초기화됨
    sregex_iterator lastMatch;

    while (curMatch != lastMatch) {
        smatch match = *curMatch;
        matches.push_back(match.str()); 
        curMatch++;
    }

    // match.str() // match된 string
    // match.prefix() // match된 string 앞 부분
    // match.suffix() // match된 string 뒷 부분

    return matches;
}

vector<string> getCaptures(string str, regex reg)
{
    vector<string> matches;

    // sregex_iterator 내, begin(), end(), reg를 저장하여 순회 가능
    sregex_iterator curMatch(str.begin(), str.end(), reg);
    // lastMatch는 end로 초기화됨
    sregex_iterator lastMatch;

    while (curMatch != lastMatch) {
        smatch match = *curMatch;
        matches.push_back(match[1]); // capturing group 1번 사용!
        curMatch++;
    }

    // match.str() // match된 string
    // match.prefix() // match된 string 앞 부분
    // match.suffix() // match된 string 뒷 부분

    return matches;
}

int main()
{
    vector<string> matches;

    string str = "Hi My Name is Hit";
    regex reg("Hi[^ ]?");

    matches = getMatches(str, reg);
    for (int i = 0; i < matches.size(); i++) {
        cout << matches[i] << endl;
    }

    // 패턴 검색 후, 검색 내용 중 Capture
    // http://www.youtu.be/-ZClicWm0zM\n\
    // https://www.youtu.be/-ZClicWm1zM\n\
    // https://youtu.be/-ZClicWm2zM\n\
    // youtu.be/-ZClicWm3zM"
    // 위에서 ID만 추출..
    regex reg("(?:https?:\\/\\/)?(?:www\\.)?youtu\\.be\/([a-zA-Z0-9-]+)");

    matches = getCaptures(str, reg);
    for (int i = 0; i < matches.size(); i++) {
        cout << matches[i] << endl;
    }

    return 0;
}

알고리즘

custom sort

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Data {
    int x, y;
};

// 1순위 : x 오름차순 정렬, 2순위 y 오름차순 정렬
bool compare(Data a, Data b)
{
    if (a.x < b.x)
        return true;

    if ((a.x == b.x) && (a.y < b.y))
        return true;

    return false;
}

int main()
{
    vector<Data> vect = { {1, 2}, {2, 3}, {4, 5}, {5, 1}, {3, 4}, {2, 5}, {7, 1}, {7, 2}, {1, 5}};

    sort(vect.begin(), vect.end(), compare);

    cout << "hello" << endl;

    return 0;
}

lower_bound/upper_bound, 이진탐색

• 중복되는 것이 없을 땐, lower_bound로 구하고...
• 중복되는 것이 있을 땐, upper_bound - lower_bound
• 주의 : upper_bound는 target의 다음 iterator 반환! (개방)

#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> uniqueVect = { 2, 4, 3, 1, 5, 9, 8, 7 };
    vector<int> overlapVect = { 2, 4, 3, 1, 4, 9, 4, 3 };

    // 1. 2진 탐색 이전 정렬
    sort(uniqueVect.begin(), uniqueVect.end());
    sort(overlapVect.begin(), overlapVect.end());

    // unique Vect binary search
    int target = 4;
    auto targetIt = lower_bound(uniqueVect.begin(), uniqueVect.end(), target);
    int targetIdx = targetIt - uniqueVect.begin();

    // overlap Vect count
    target = 4;
    auto targetLowerIt = lower_bound(overlapVect.begin(), overlapVect.end(), target); // 4를 가리키는 Iterator 반환
    auto targetUpperIt = upper_bound(overlapVect.begin(), overlapVect.end(), target); // 4가 끝나고 다음 Iterator 반환 (개방)
    int count = targetUpperIt - targetLowerIt;


    return 0;
}

다익스트라

• 한 노드에서 다른 모든 노드들까지 최단거리를 구함
• 모든 간선이 자연수여야 함.
• 그리드 알고리즘, 방문하지 않은 노드 중 최단거리인 노드를 중심으로 최단거리를 업데이트
  • 방문하지 않은 노드 중 최단거리 == 이미 업데이트가 되지 않는 상태임

#include <queue>
#include <iostream>

using namespace std;

#define NUM_OF_NODE 6

// 1번 노드 부터라고 가정
// 이코테 다익스트라 예제 간선 구현
int costMap[NUM_OF_NODE + 1][NUM_OF_NODE + 1] = {
//   0,1,2,3,4,5,6
    {0,0,0,0,0,0,0}, // 0
    {0,0,2,5,1,0,0}, // 1
    {0,0,0,3,2,0,0}, // 2
    {0,0,3,0,0,0,5}, // 3
    {0,0,0,3,0,1,0}, // 4
    {0,0,0,1,0,0,2}, // 5
    {0,0,0,0,0,0,0}, // 6
};

vector<int> minCosts;
bool isVisit[NUM_OF_NODE];

struct CostInfo {
    int node;
    int cost;
};

struct compare { // for cost min heap
    bool operator()(CostInfo a, CostInfo b) {
        return a.cost > b.cost;
    }
};

void initVars()
{
    minCosts.clear();

    for (int i = 0; i < NUM_OF_NODE; i++)
        isVisit[i] = false;
}

void initMinCosts(int startNode, int numOfNode)
{
    for (int i = 0; i < numOfNode + 1; i++) {
        minCosts.push_back(INT_MAX);
    }
    minCosts[startNode] = 0;
}

void dijkstra(int startNode, int numOfNode)
{
    initVars();

    priority_queue<CostInfo, vector<CostInfo>, compare> heap;
    initMinCosts(startNode, numOfNode);
    heap.push({ startNode, 0 });

    while (heap.empty() == false) {
        CostInfo ci = heap.top();
        heap.pop();

        if (isVisit[ci.node] == true)
            continue;

        isVisit[ci.node] = true;

        for (int target = 1; target <= numOfNode ; target++) {
            if ((costMap[ci.node][target] != 0) && (isVisit[target] == false)) {
                int curMinCost = minCosts[target];
                int newCost = minCosts[ci.node] + costMap[ci.node][target];

                if (newCost < curMinCost) {
                    minCosts[target] = newCost;
                    heap.push({ target, newCost });
                }
            }
        }
    }
}

int main()
{
    int startNode = 1;
    int numOfNode = 6;
    dijkstra(startNode, numOfNode);

    for (int i = 0; i < minCosts.size(); i++) {
        cout << minCosts[i] << endl;
    }

    return 0;
}

기타 최단거리 알고리즘

• 플로이드 워셜 알고리즘
  • 모든 점에서 min(Pab, Pak + Pkb)를 구해 거리를 업데이트 하는 방식
  • 모든 점간의 최소거리를 구함 (최소 거리 테이블이 나옴)

DFS, BFS

#include <vector>
#include <iostream>
#include <queue>

#define MAX_SIZE 10

using namespace std;

vector<vector<int>> maze = {
    {1,0,1,1,1,1},
    {1,0,1,0,1,0},
    {1,0,1,1,1,1},
    {1,1,1,0,1,1},
};

int numOfX = 6;
int numOfY = 4;

pair<int, int> startPos = { 0, 0 };
pair<int, int> endPos = { 5, 3 };

bool isVisit[MAX_SIZE][MAX_SIZE];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

vector<pair<int, int>> path;

bool isValidXY(int x, int y)
{
    if ((x < 0) || (y < 0) || (x >= numOfX) || (y >= numOfY))
        return false;
    return true;
}

void dfs(int x, int y)
{
    // 진입시 바로 할 일
    isVisit[x][y] = true;
    path.push_back({x, y});

    // 종료조건 + 종료시 처리할 것 goto
    if ((x == endPos.first) && (y == endPos.second)) {
        for (int i = 0; i < path.size(); i++) {
            cout << "[" <<path[i].first << "," << path[i].second << "]";
        }
        cout << endl;
        goto exit;
    }

    // 다음 노드 진입 및 가지치기
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        // vector<vector<int>> 의 경우 x,y가 아닌 y, x 순으로 접근 필요
        if (isValidXY(nx, ny) && (maze[ny][nx] == 1) && (isVisit[nx][ny] == false)) {
            dfs(nx, ny);
        }
    }

    // 종료시 처리할  것
exit:
    isVisit[x][y] = false;
    path.pop_back();
}

struct Pos {
    int x, y;
    int level;
};

void bfs(int x, int y)
{
    queue<Pos> q;
    q.push({ x, y, 1});
    // 진입시 바로 할 일
    isVisit[x][y] = true;

    while (!q.empty()) {
        Pos curPos = q.front();
        q.pop();

        // 종료조건
        if ((curPos.x == endPos.first) && (curPos.y == endPos.second)) {
            cout << curPos.level << endl;
            break;
        }

        // 다음 노드 진입 및 가지치기
        for (int i = 0; i < 4; i++) {
            int nx = curPos.x + dx[i];
            int ny = curPos.y + dy[i];
            // vector<vector<int>> 의 경우 x,y가 아닌 y, x 순으로 접근 필요
            if (isValidXY(nx, ny) && (maze[ny][nx] == 1) && (isVisit[nx][ny] == false)) {
                q.push({nx, ny, curPos.level + 1});
                // 집입시 바로 할 일
                isVisit[nx][ny] = true;
            }
        }
    }
}

int main()
{
    //dfs(0, 0);
    //bfs(0, 0);
    return 0;
}

DFS 조합

#include <iostream>
#include <vector>

using namespace std;

vector<char> elements = { 'A', 'B', 'C', 'D' };
vector<char> path;

void dfs(int preIdx)
{
    // print path
    if (path.size() != 0) { // not include anything yet
        cout << path.size() << " : ";
        for (int i = 0; i < path.size(); i++) {
            cout << path[i] << " ";
        }
        cout << endl;
    }

    for (int i = preIdx + 1; i < elements.size(); i++) {
        path.push_back(elements[i]);
        dfs(i);
        path.pop_back();
    }
}

int main()
{
    dfs(-1);
    return 0;
}

union/intersection, 합집합/교집합

set_union, set_intersection 이전에 반드시 sort 필요함.

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

vector<string> getUnion(vector<string> &vect1, vector<string> &vect2)
{
    vector<string> buff(vect1.size() + vect2.size());

    sort(vect1.begin(), vect1.end());
    sort(vect2.begin(), vect2.end());

    auto iter = set_union(
        vect1.begin(), vect1.end(),
        vect2.begin(), vect2.end(),
        buff.begin()
    );

    buff.erase(iter, buff.end());

    return buff;
}

vector<string> getIntersection(vector<string>& vect1, vector<string>& vect2)
{
    vector<string> buff(vect1.size() + vect2.size());

    sort(vect1.begin(), vect1.end());
    sort(vect2.begin(), vect2.end());

    auto iter = set_intersection(
        vect1.begin(), vect1.end(),
        vect2.begin(), vect2.end(),
        buff.begin()
    );

    buff.erase(iter, buff.end());

    return buff;
}

int main()
{
    vector<string> vect1 = { "cd", "ab", "bc",};
    vector<string> vect2 = { "cd", "fg", "ef", };

    vector<string> uni = getUnion(vect1, vect2);
    vector<string> inter = getIntersection(vect1, vect2);

    return 0;
}

• 부족한 점, 알아둬야할 점 정리해서 시험보기 전 보충하기!

1번

#include <iostream>
#include <map>
#include <vector>
#include <sstream>

using namespace std;

map<string, string> lastNameMap;

vector<string> split(string input, char delimiter) {
    vector<string> answer;
    stringstream ss(input);
    string temp;

    while (getline(ss, temp, delimiter)) {
        answer.push_back(temp);
    }

    return answer;
}

void initLastNameMap(vector<string>& record)
{
    for (int i = 0; i < record.size(); i++) {
        vector<string> words = split(record[i], ' ');
        if ((words[0] == "Enter") || (words[0] == "Change")) {
            lastNameMap[words[1]] = words[2];
        }
    }
}
//sdfdfdfssdfsdfsdfdf
string translate(string record)
{
    string result = "";
    vector<string> words = split(record, ' ');
    if (words[0] == "Enter") {
        result = lastNameMap[words[1]] + "님이 들어왔습니다.";
    }
    else if (words[0] == "Leave") {
        result = lastNameMap[words[1]] + "님이 나갔습니다";
    }
    else {
        // Do nothing
    }
    return result;
}

vector<string> solution(vector<string>& record)
{
    vector<string> answer;

    initLastNameMap(record);

    for (int i = 0; i < record.size(); i++) {
        answer.push_back(translate(record[i]));
    }

    return answer;
}

int main()
{
    vector<string> record = {
        "Enter uid1234 Muzi",
        "Enter uid4567 Prodo",
        "Leave uid1234",
        "Enter uid1234 Prodo",
        "Change uid4567 Ryan"
    };

    vector<string> result = solution(record);

    cout << result[0] << endl;

    return 0;
}

2번

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct FailRate {
    int stage;
    double rate;
};

bool compare(FailRate a, FailRate b)
{
    if (a.rate > b.rate)
        return true;

    if (a.rate == b.rate) {
        if (a.stage < b.stage) {
            return true;
        }
    }

    return false;
}

double getRate(int n, int curStage, vector<int>& stages)
{
    int numOfPlayers = 0;
    int numOfFail = 0;

    for (int i = 0; i < stages.size(); i++) {
        if (stages[i] >= curStage) {
            numOfPlayers++;
        }
        if (stages[i] == curStage) {
            numOfFail++;
        }
    }

    if (numOfPlayers == 0)
        return 0;

    return numOfFail / double(numOfPlayers);
}

void calcFailRate(int n, vector<int>& stages, vector<FailRate>& failRates)
{
    for (int stage = 1; stage <= n; stage++) {
        double rate = 0;
        rate = getRate(n, stage, stages);
        failRates.push_back({stage, rate});
    }
}

vector<int> solution(int n, vector<int> stages)
{
    vector<FailRate> failRates;
    vector<int> result;

    calcFailRate(n, stages, failRates);
    sort(failRates.begin(), failRates.end(), compare);

    for (int i = 0; i < failRates.size(); i++) {
        result.push_back(failRates[i].stage);
    }

    return result;
}

int main()
{
    int n = 5;
    vector<int> stages = { 2, 1, 2, 6, 2, 4, 3, 3 };
    vector<int> result = solution(n, stages);

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << endl;
    }

    return 0;
}

3번

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<int> path;
int numOfRows, numOfCols;

int isUniquePath(vector<vector<string>>& relation, vector<int> &path)
{
    vector<string> keys;

    for (int row = 0; row < numOfRows; row++) {
        vector<string> rowStrs = relation[row];
        string key = "";
        for (int i = 0; i < path.size(); i++) {
            key += rowStrs[path[i]];
        }
        keys.push_back(key);
    }

    int originSize = keys.size();
    sort(keys.begin(), keys.end());
    keys.erase(unique(keys.begin(), keys.end()), keys.end());
    int uniqueSize = keys.size();

    if (originSize == uniqueSize) {
        return true;
    }

    return false;

}

int dfs(vector<vector<string>>& relation, int preIdx)
{
    if (path.size() != 0) {
        if (isUniquePath(relation, path)) {
            return 1;
        }
    }

    int sum = 0;
    for(int i = preIdx +1 ; i < numOfCols ; i++) {
        path.push_back(i);
        sum += dfs(relation, i);
        path.pop_back();
    }

    return sum;
}

int solution(vector<vector<string>>& relation)
{
    numOfRows = relation.size();
    numOfCols = relation[0].size();

    int answer = dfs(relation, -1);
    cout << answer << endl;

    return answer;
}

int main()
{
    vector<vector<string>> relation = {
        {"100", "ryan", "music", "2"},
        {"200", "apeach", "math", "2"},
        {"300", "tube", "computer", "3"},
        {"400", "con", "computer", "4"},
        {"500", "muzi", "music", "3"},
        {"600", "apeach", "music", "2"},
    };

    int answer = solution(relation);

    return 0;
}

4번

#include <iostream>
#include <vector>
#include <list>

using namespace std;

struct Food {
    int num;
    int restTime;
};

list<Food> foods;

void initFoods(vector<int> &foodTimes)
{
    for (int i = 0; i < foodTimes.size(); i++) {
        foods.push_back({ i + 1, foodTimes[i] });
    }
}

int eatFoodsUntil(int k)
{
    auto foodIt = foods.begin();
    for (int i = 0; i < k; i++) {
        foodIt->restTime--;
        if (foodIt->restTime == 0)
            foodIt = foods.erase(foodIt);
        else
            foodIt++;

        if (foodIt == foods.end()) {
            foodIt = foods.begin();
        }
    }

    return foodIt->num;
}

int solution(vector<int> foodTimes, int k)
{
    initFoods(foodTimes);
    return eatFoodsUntil(k);
}

int main()
{
    vector<int> foodTimes = { 3, 1, 2 };
    int k = 5;
    int answer = solution(foodTimes, k);

    return 0;
}

5번

#include <vector>
#include <iostream>
#include <algorithm>

#define MAX_NODES 10001

using namespace std;

struct Node {
    int num;
    int x, y;
    Node* left, * right;
};

Node nodes[MAX_NODES];
int numOfNodes;
Node* root;

void initNodes(vector<pair<int, int>>& nodeinfo)
{
    numOfNodes = nodeinfo.size();

    for (int i = 0; i < numOfNodes; i++) {
        nodes[i].num = i + 1;
        nodes[i].x = nodeinfo[i].first;
        nodes[i].y = nodeinfo[i].second;
        nodes[i].left = NULL;
        nodes[i].right = NULL;
    }
}

bool cmp(Node a, Node b)
{
    return a.x < b.x;
}

void sortNodesByX()
{
    sort(nodes, nodes + numOfNodes, cmp);
}

Node* makeSubTree(Node* arr, int size)
{
    if (size == 0)
        return NULL;

    int maxY = 0;
    int maxYIdx = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i].y > maxY) {
            maxY = arr[i].y;
            maxYIdx = i;
        }
    }

    Node* parent = &arr[maxYIdx];

    parent->left = makeSubTree(arr, maxYIdx);
    parent->right = makeSubTree(arr + maxYIdx + 1, size - maxYIdx -1);

    return parent;
}

void dfs(vector<int>& prePath, vector<int>& postPath, Node* node)
{
    if (node == NULL)
        return;

    prePath.push_back(node->num);
    dfs(prePath, postPath, node->left);
    dfs(prePath, postPath, node->right);
    postPath.push_back(node->num);
}

vector<vector<int>> solution(vector<pair<int, int>>& nodeinfo)
{
    initNodes(nodeinfo);
    sortNodesByX();
    Node *rootNode = makeSubTree(nodes, numOfNodes);

    vector<int> prePath, postPath;
    dfs(prePath, postPath, rootNode);

    return { prePath, postPath };
}

int main()
{
    vector<pair<int, int>> nodeinfo = {
        {5, 3},
        {11, 5},
        {13, 3},
        {3, 5},
        {6, 1},
        {1, 3},
        {8, 6},
        {7, 2},
        {2, 2},
    };

    vector<vector<int>> result = solution(nodeinfo);

    return 0;
}

• set_union, set_intersection 이전에 sort 필요함!

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void capitalize(string& str)
{
    for (auto& c : str)
        c = toupper(c);
}

bool is_text(char c)
{
    if ((c >= 'A') && (c <= 'Z'))
        return true;
    return false;
}

void getVect(string& str, vector<string> &strVect)
{
    for (int i = 0; i < str.size() - 1; i++) {
        // 둘 다 대문자
        if (is_text(str[i]) && is_text(str[i+1])) {
            strVect.push_back({ str[i], str[i + 1], '\0' });
        }
    }
}

int getInterSize(vector<string>& str1Vect, vector<string>& str2Vect)
{
    vector<string> buff(str1Vect.size() + str2Vect.size());

    sort(str1Vect.begin(), str1Vect.end());
    sort(str2Vect.begin(), str2Vect.end());

    auto iter = set_intersection(
        str1Vect.begin(), str1Vect.end(),
        str2Vect.begin(), str2Vect.end(),
        buff.begin());
    buff.erase(iter, buff.end());

    return buff.size();
}

int getUniSize(vector<string>& str1Vect, vector<string>& str2Vect)
{
    vector<string> buff(str1Vect.size() + str2Vect.size());

    sort(str1Vect.begin(), str1Vect.end());
    sort(str2Vect.begin(), str2Vect.end());

    auto iter = set_union(str1Vect.begin(), str1Vect.end(),
        str2Vect.begin(), str2Vect.end(), buff.begin());
    buff.erase(iter, buff.end());

    return buff.size();
}

int solution(string str1, string str2)
{
    double answer = 0;

    capitalize(str1);
    capitalize(str2);

    vector<string> str1Vect, str2Vect;

    getVect(str1, str1Vect);
    getVect(str2, str2Vect);

    double interSize = getInterSize(str1Vect, str2Vect);
    double uniSize = getUniSize(str1Vect, str2Vect);

    if ((interSize == 0) && (uniSize == 0)) {
        answer = 1;
    }
    else {
        answer = interSize / uniSize;
    }

    return int(answer * 65536);
}

int main()
{
    string str1 = "aa1+aa2";
    string str2 = "AAAA12";

    int answer = solution(str1, str2);

    cout << answer << endl;

    return 0;
}

미로탈출 & 최단거리

• BFS 이용시 queue에 저장할 때, level을 함께 저장하여 최단거리 알아냄

#include <iostream>
#include <queue>

using namespace std;

struct Point {
    int x, y;
    int level;
};

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool isVisit[7][6];

int solution(int n, int m, int(*map)[6])
{
    queue<Point> q;

    q.push({ 1, 1, 1});
    isVisit[1][1] = true;

    while (q.empty() == false) {
        Point p = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            if ((map[nx][ny] == 1) && (isVisit[nx][ny] == false)) {
                isVisit[nx][ny] = true;
                q.push({ nx, ny, p.level + 1 });
            }

            if ((nx == n) && (ny == m))
                return p.level + 1;
        }

    }
}

int main()
{
    int n = 5, m = 4;
    int map[7][6] = {
        {0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 1, 1, 1, 1, 0},
        {0, 1, 0, 0, 1, 0},
        {0, 1, 1, 1, 1, 0},
        {0, 0, 0, 0, 0, 0},
    };

    int answer = solution(n, m, map);

    cout << answer << endl;

    return 0;
}

2018 코딩테스트 문제 4 연습

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <stdio.h>

#define _CRT_SECURE_NO_WARNINGS

using namespace std;

int c2i(char c)
{
    return c - '0';
}

int strToMin(string sTime)
{
    int hour = c2i(sTime[0]) * 10 + c2i(sTime[1]);
    int min = c2i(sTime[3]) * 10 + c2i(sTime[4]);

    return min + (hour * 60);
}

void initMinTimeTable(list<int> &minTimeTable, vector<string>& timetable)
{
    for (int i = 0; i < timetable.size(); i++) {
        minTimeTable.push_back(strToMin(timetable[i]));
    }
}

int getCurTime(int idx, int intervalTime)
{
    int baseHour = 9;
    return (baseHour * 60) + (intervalTime * (idx - 1));
}

bool isPossibleTimeToRide(int min, int curTime)
{
    if (curTime >= min) {
        return true;
    }
    return false;
}

void getOnTheBus(int curTime, int limit, list<int>& minTimeTable)
{
    for (int i = 0; i < limit; i++) {
        if (isPossibleTimeToRide(*minTimeTable.begin(), curTime)) {
            minTimeTable.erase(minTimeTable.begin());
        }
        else {
            break;
        }
    }
}

string minToStr(int min)
{
    int hour = min / 60;
    int minumtes = min % 60;
    char str[20];

    sprintf_s(str, 6, "%02d:%02d", hour, minumtes);

    string s = str;

    return s;
}

bool cmp(int a, int b)
{
    return a < b;
}

string solution(int n, int t, int m, vector<string>& timetable)
{
    int numOfBus = n;
    int intervalTime = t;
    int maxLimit = m;
    list<int> minTimeTable;
    int answerMin = 0;

    sort(timetable.begin(), timetable.end());
    initMinTimeTable(minTimeTable, timetable);
    //sort(minTimeTable.begin(), minTimeTable.end(), cmp);

    for (int i = 1; i <= numOfBus; i++) {
        int curTime = getCurTime(i, intervalTime);

        if (i == numOfBus) { // last bus
            getOnTheBus(curTime, maxLimit - 1, minTimeTable);
            if (minTimeTable.size() == 0) {
                answerMin = curTime;
                break;
            }

            if (isPossibleTimeToRide(*minTimeTable.begin(), curTime)) {
                answerMin = *minTimeTable.begin() - 1;
                break;
            }
            else {
                answerMin = curTime;
                break;
            }
        }
        else {
            getOnTheBus(curTime, maxLimit, minTimeTable);
        }
    }

    return minToStr(answerMin);
}

int main()
{
    int n = 10;
    int t = 60;
    int m = 45;
    vector<string> timetable = { "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59",
        "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59",
        "23:59"};
    string answer = solution(n, t, m, timetable);

    std::cout << answer << endl;

    return 0;
}

• isVisit처리 중요.
• DFS 스택을 사용해도 좋지만, 재귀함수를 이용하는 것이 생각이 편함.
• BFS는 Queue를 사용해, Queue가 빌때까지 동작...

음료수 얼려먹기 문제 풀이

DFS

#include <iostream>

using namespace std;

#define MAX_SIZE 5

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool isVisit[MAX_SIZE][MAX_SIZE];
int map[MAX_SIZE][MAX_SIZE] = {
    {1, 1, 1, 1, 1},
    {0, 0, 1, 1, 0},
    {0, 0, 0, 1, 1},
    {1, 1, 1, 1, 1},
    {0, 0, 0, 0, 0},
};

bool isValidXY(int x, int y)
{
    if (x < 0)
        return false;
    if (y < 0)
        return false;
    if (x >= MAX_SIZE)
        return false;
    if (y >= MAX_SIZE)
        return false;

    if (map[x][y] == 1)
        return false;

    return true;
}

void dfs(int x, int y)
{
    isVisit[x][y] = true;
    int nx, ny;

    for (int i = 0; i < 4; i++) {
        nx = x + dx[i];
        ny = y + dy[i];
        if (isValidXY(nx, ny)) {
            if (isVisit[nx][ny] == false) {
                dfs(nx, ny);
            }
        }
    }
}

int main()
{
    int cnt = 0;
    for (int x = 0; x < MAX_SIZE; x++) {
        for (int y = 0; y < MAX_SIZE; y++) {
            if ((isVisit[x][y] == false) && (map[x][y] == 0)){
                cnt++;
                dfs(x, y);
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

BFS

#include <iostream>
#include <queue>

using namespace std;

#define MAX_SIZE 5

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool isVisit[MAX_SIZE][MAX_SIZE];
int map[MAX_SIZE][MAX_SIZE] = {
        {1, 1, 1, 1, 1},
        {0, 0, 1, 1, 0},
        {0, 0, 0, 1, 1},
        {1, 1, 1, 1, 1},
        {0, 0, 0, 0, 0},
};

bool isValidXY(int x, int y)
{
    if (x < 0)
        return false;
    if (y < 0)
        return false;
    if (x >= MAX_SIZE)
        return false;
    if (y >= MAX_SIZE)
        return false;

    if (map[x][y] == 1)
        return false;

    return true;
}

struct Point {
    int x, y;
};

void bfs(int x, int y)
{
    queue<Point> q;

    isVisit[x][y] = true;
    q.push({ x, y });

    while (q.empty() == false) {
        Point p = q.front();
        q.pop();

        int nx, ny;
        for (int i = 0; i < 4; i++) {
            nx = p.x + dx[i];
            ny = p.y + dy[i];
            if (isValidXY(nx, ny)) {
                if (isVisit[nx][ny] == false) {
                    isVisit[nx][ny] = true;
                    q.push({ nx, ny });
                }
            }
        }
    }
}

int main()
{

    int cnt = 0;
    for (int x = 0; x < MAX_SIZE; x++) {
        for (int y = 0; y < MAX_SIZE; y++) {
            if ((isVisit[x][y] == false) && (map[x][y] == 0)) {
                cnt++;
                bfs(x, y);
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

• 파라메트릭 서치 : 최적의 해를 구할 때, 결정문제(예, 아니오)로 바꾸어 해결
  • 예) 가래떡 문제.. 선형적이 아닌 2진 탐색으로 해결
• 정렬된 벡터에서 4의 갯수, 5의 갯수를 구할 떄, lower_boud/upper_bound를 확인하여 빼준다.

2018 코딩테스트 문제 3

#include <iostream>
#include <vector>
#include <string>
#include <list>

using namespace std;

list<string> cache;

int get_data(string city, int cacheSize)
{
    int time;

    auto it = find(cache.begin(), cache.end(), city);
    if (it != cache.end()) { // exist
        time = 1;
        cache.erase(it);
    }
    else {
        time = 5;
    }
    cache.push_back(city);

    if (cache.size() > cacheSize) {
        cache.erase(cache.begin());
    }

    return time;
}

int main()
{
    int cacheSize=2;
    vector<string> cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA",
        "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};

    int sum = 0;
    for (int i = 0; i < cities.size(); i++) {
        sum += get_data(cities[i], cacheSize);
    }

    cout << sum << endl;

    return 0;
}

• 정규표현식 관련 글 따로 작성함.

2018 코딩테스트 문제2번을 풀면서 잘못했던 점은.. 문자열만 자를 생각부터 먼저하다보니 문제를 자세히 보지 않았다... 자세히 봤으면 자르고 시작하는 것이 아니었다..

예제를 보고 내가 문제를 잘 이해했는지 꼭 살펴보자!

• 너무 복잡하게 생각하지말고 단순하게 풀자!
• 어차피... 미리 생각 안해놓으면 코드 짜면서 다시 생각해야하니깐... 그리고 생각보다 문제가 복잡하니깐.. 미리 거의 손으로 로직은 짜놓고 코드로 옮기자!
• 문제 정말 이해 잘하자... 급할 수록 돌아가자...!!
• 문제 미리 다 짜 놓으면 오히려 빠르다는 사실을 잊지말자!
  • 오래 끌었던 이유는 문제를 제대로 이해 안해서이다.. 사실 제대로 봤으면 진작에 풀었을 것이다.... 제대로 확인하자!!

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<char> options;
vector<int> scores;

void init_options(string &result)
{
    for (int i = 0; i < 4; i++) {
        options.push_back('-');
    }

    int idx = 2;

    for (int i = result.length() - 1 ; i >= 0; i--) {
        if ((result[i] == '*') || (result[i] == '#')) {
            options[idx] = result[i];
        }
        if ((result[i] == 'S') || (result[i] == 'D') || (result[i] == 'T')) {
            idx--;
        }
    }
}

bool is_digit(char c)
{
    if ((c >= '0') && (c <= '9'))
        return true;

    return false;
}

int get_score(string score, char square)
{
    int iscore = stoi(score);
    if (square == 'S')
        return iscore;
    else if (square == 'D')
        return iscore * iscore;
    else
        return iscore * iscore * iscore;
}

void init_scores(string& result)
{
    int idx = 0;
    string score;
    for (int i = 0; i < result.length(); i++) {
        if (is_digit(result[i])) {
            score.push_back(result[i]);
        }
        if ((result[i] == 'S') || (result[i] == 'D') || (result[i] == 'T')) {
            idx++;
            scores.push_back(get_score(score, result[i]));
            score = "";
        }
    }
}

int solution(string& result)
{
    init_options(result);
    init_scores(result);

    // calc answer
    int sum = 0;
    for (int i = 0; i < 3; i++) {
        int score = 0;
        switch (options[i]) {
        case '-':
            score = scores[i];            
            break;
        case '*':
            score = scores[i] * 2;
            break;
        case '#':
            score = scores[i] * -1;
            break;
        }

        if (options[i + 1] == '*')
            score *= 2;

        sum += score;
    }

    return sum;
}

int main()
{
    string result = "1D2S3T*";
    int answer = solution(result);
    return 0;
}

1. 기본연산자

   • . : 개행무자를 제외한 모든 문자
   • a : 문자 a
   • ab : 문자열 ab
   • x|y : x나 y
   • \특수문자 : ^+{}$()[]|-?.* 과 같은 특수문자

2. 캐릭터 클래스

   • [a-d] : a, b, c, d 중 문자 1개
   • [^a-d] : a, b, c, d를 제외한 문자 1개
   • \d : 숫자(digit) 1개
   • \D : 숫자가 아닌 개체 1개
   • \s : 공백 1개
   • \S : 공백이 아닌 개체 1개
   • \w : 알파벳 또는 숫자 1개
   • \W : 알파벳이나 숫자가 아닌 개체1개

3. 양적 연산자

   • x* : 0개 이상의 x
   • x+ : 1개 이상의 x
   • x? : 0이나 1개인 x
   • x{2} : x가 정확히 2개
   • x{2,5} : 2개에서 5개 사이의 x

4. 이스케이프 문자

   • \n : 개행
   • \r : 캐리지 리턴(현재 줄의 맨 앞)
   • \t : 탭

5. 위치 지정

   • ^ : 문자열의 처음
   • \b : 단어 경계
   • \B : 비단어 경계
   • $ : 문자열의 끝

6. 그룹

   • (x) : 캡처링 그룹
   • (?:x) : 비캡처링 그룹

regex 사용

• std::regex_match(str, re)
  • reg 패턴이 전체 str과 매칭여부 true, false 리턴
• std::regex_search(str, re)
  • reg 패턴이 str내 존재여부 true, false 리턴
• std::regex_search(str, smatches, re)
  • reg 패턴을 str내에서 찾아 smatches에 담아줌

vector<string> split(string result)
{
    vector<string> results;
    regex reg("[0-9]*[SDT][*#]*");

    smatch what;
    for (smatch m; regex_search(result, m, reg); result = m.suffix()) {
        results.push_back(m.str());
    }

    return results;
}

• C, C++ 기준 대략적인 1초 계산방법
  • O(N) : 1000만
  • O(NlogN) : 10만
  • O(N^2) : 2000
  • O(N^3) : 500

그리드, 구현

2018 코딩테스트 문제1

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string merge_arr(int a, int b, int n)
{
    int tot = a | b;
    string str;
    for (int i = n -1; i >= 0; i--) {
        char c = (tot >> i) & 1 ? '#' : ' ';
        str.push_back(c);
    }
    return str;
}

vector<string> solution(int n, vector<int> arr1, vector<int> arr2)
{
    vector<string> answer;

    for (int i = 0; i < n; i++) {
        answer.push_back(merge_arr(arr1[i], arr2[i], n));
    }

    return answer;
}

int main()
{
    int n = 5;
    vector<int> arr1 = { 9, 20, 28, 18, 11 };
    vector<int> arr2 = { 30, 1, 21, 17, 28 };

    solution(n, arr1, arr2);
    return 0;
}

일단, 풀어본 느낌으로는 만만치 않다고 생각이 들었으며, 연습이 많이 필요하다고 느꼇다.

• 부족한 점
  • 문제풀이 방법을 좀 더 생각한 뒤에 코딩을 했으나 모자란 면이 있었음.
  • 문제풀이 방법이 올바른지 실제 예제에 답해보지 않았다가.. 나중에 이해한 내용이 달랐다는 것을 깨달아서 시간이 더 오래걸림!!
  • 5시간동안 7문제 -> 후기 찾아보니 보통 3~4가 커트라인이었다고 함...
    • 그러니 너무 조급해 하지말고, 문제 이해를 완벽히(예제까지) 확실히 보고 설계하고.. 코딩한다!!

-> 기존에 abc, err := somefunc()를 err가 여러번 선언된것 처럼 생각했는데 가능했는지를 이해함.

코딩테스트 준비

2021 카카오 신입공채 1차 온라인 테스트

• 문제 1번 풀이함
  • 잘 못 했던 부분
    • 너무 조급하게 코딩하려고 해서 오히려 늦게 코드를 구현함
    • 완전하게 잘 짜려고 하는 욕심을 조금은 버려야 할듯.. (시간 내 문제 풀이를 해야하니.. 만약에 시간내 다 풀었다면 그때 와서 다시 최적화 하자!)코드를 입력하세요

• Short Variable Declaration Operator
• [Difference between var keyword and short declaration operator in Golang]
• Discovery Go 도서

Short Varaible Declaration Operator(:=)

연산자 := 는 var 키워드 및 type을 생략하고 변수를 선언할 때 사용한다. 이 연산자의 주목적은 함수 내의 local 변수의 초기화 및 선언하고 변수의 스코프를 좁히기 위한 것이다. 변수의 타입은 식의 타입(오른쪽에 무엇이 있는가)에 따라 정의된다. 정리하면 go에서는 변수를 생성하는 두 가지 방법이 있다.

• var 키워드 사용하는 방법
• := 를 사용하는 방법

Short Variable Operator 사용 방법

변수이름 := 식 또는 값

var 키워드를 사용하면 선언과 초기화를 따로 할 수 있지만, :=를 사용하면 선언과 초기화를 동시에 해야한다.

예제

package main

import "fmt"

func main() {
    i := 5
    str := "Hello, World"
    fmt.Println(i)
    fmt.Println(str)
}

Short Declaration Operator를 사용하여 여러 개의 변수 선언하기

Short Declaration Operator를 사용하면 같은 타입 혹은 다른 타입의 변수를 한 번에 여러개 선언할 수 있다.

예제1 :

package main

import "fmt"

func main() {
    a, b, c := "Hello", 5, 2.4
    fmt.Printf("a : %s, type of a : %T\n", a, a)
    fmt.Printf("b : %d, type of b : %T\n", b, b)
    fmt.Printf("c : %f, type of c : %T\n", c, c)
}

결과 :

a : Hello, type of a : string
b : 5, type of b : int
c : 2.400000, type of c : float64

예제2 :

package main

import "fmt"

func main() {
    a, b := 1, 2
    a := 4           // error
    c, b := 3, 4     // Not error
    d, b := 5, "abc" // error

    fmt.Printf("%d, %T\n", a, a)
    fmt.Printf("%d, %T\n", b, b)
    fmt.Printf("%d, %T\n", c, c)
    fmt.Printf("%d, %T\n", d, d)
}

• a := 4 가 에러인 이유는 이미 a가 한 번 선언된 상태이기 때문에 재선언을 할 수 없어서이다.
• c, b := 3, 4가 에러가 아닌 이유는 b는 이미 선언되었지만, c는 한 번도 선언되지 않았기 때문에 c는 새로 선언하고, b는 값만 대입된다.
• d, b := 5, "abc"가 에러인 이유는 d는 한 번도 선언되지 않았지만, b가 기존에 정수형 타입으로 이미 선언된 상태이기 때문에 타입을 바꿀 수 없어서 이다.

여러개의 리턴 값을 가지는 함수에도 := 연산자 사용이 가능하다.

package main

import "fmt"

func next(n int) (int, int) {
    return n + 1, n + 2
}

func main() {
    next1, next2 := next(1)
    fmt.Println(next1, next2)
}

지역(Local) 변수 / 전역(Global) 변수

:= 연산자는 block-level scope 를 가지는 지역 변수만 선언 가능하다. 일반적으로 지역 변수는 함수 block 내에서 선언된다. 만약 전역 변수를 :=로 선언하려고 하면 에러가 날 것이다.

package main

import "fmt"

a := 3 // error

func main() {
    b := 5 // Not error
}

• Go 자료형 해석

코딩테스트 준비

• C++ STL 정리
  • string
  • vector / list /deque

• 리소스 파일 : input.txt, output.txt 생성
• 프로젝트>속성>구성 속성>디버깅>명령인수에 아래 내용 입력

<input.txt >output.txt

단축키

• 위치 접근 : O(1)
• 위치 접근 : O(1)
• 뒤에 원소 추가 제거 : amortized O(1) - push_back, pop_back
• 임의의 위치 원소 추가 및 제거 : O(n) - insert, erase

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec;

    vec.push_back(10); // 맨 뒤에 10 추가
    vec.push_back(20); // 맨 뒤에 20 추가
    vec.push_back(30); // 맨 뒤에 30 추가
    vec.push_back(40); // 맨 뒤에 40 추가
    vec.pop_back();    // 맨 뒤에 제거

    cout << vec.size() << endl;     // 3 : 원소 개수
    cout << vec.capacity() << endl; // 4 : 전체 사이즈, 여분 포함 - 그때 그때 다름

    vec.insert(vec.begin(), 100); // iter 자리에 100 삽입
    vec.erase(--vec.end());       // iter 자리 삭제

    // []를 통한 접근
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << ",";
    }
    cout << endl;

    // iterator를 통한 접근 - capacity 만큼 됨...
    for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); ++iter)
    {
        cout << *iter << ",";
    }
    cout << endl;

    return 0;
}

list

• double linked list
• 임의의 위치 추가, 제거 : O(1) 이나 찾는데 O(n)
• cache hit율 떨어짐
• 정말 필요한가 고민해보고 사용

#include <iostream>
#include <list>

using namespace std;

int main()
{
    list<int> li;

    li.insert(li.end(), 1);
    li.insert(li.end(), 2);
    li.insert(li.end(), 3);
    li.insert(li.end(), 4);
    li.insert(li.end(), 5);

    li.remove(3);         // 3 원소 제거
    li.erase(li.begin()); // iter 삭제

    // iter 접근
    for (list<int>::iterator iter = li.begin(); iter != li.end(); ++iter)
    {
        cout << *iter << " - ";
    }
    cout << endl;

    return 0;
}

deque

• vector와 비슷하나 앞, 뒤 추가/삭제 작업이 O(1)
• 원소들이 메모리상에서 연속적으로 존재하지 않음...
• 꽉찬 상태에서 추가할 때, vector는 새로운 공간 할당 및 복사가 이루어짐.
• deque는 기존의 원소를 복사할 필요가 없음

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque<int> dq;

    dq.push_back(10);
    dq.push_back(20);
    dq.push_back(30);
    dq.push_front(40);
    dq.push_front(50);
    dq.push_front(60);

    dq.pop_front();
    dq.pop_back();

    for (deque<int>::iterator iter = dq.begin(); iter != dq.end(); iter++)
    {
        cout << *iter << " - ";
    }
    cout << endl;

    return 0;
}