テストコードCheatsheet

試験前に覚えなければならないこと

visualstudioデバッグモードが予め1回実行されます!(ロード時間)

最適化問題は、まず最適化なしで実施され、その後、時点で最適化される.

問題を正しく読みます!正しく理解する!アルゴリズムを正しく考えた後!コード実装.

の大きな流れから、まず編成して、それから細部の流れを完成します!(コード実装が複雑であればあるほど効果的)

焦る必要はありません.わたしが難しいとほかの人も難しい

インデックスが問題と一致する場合、デバッグ時に直感的に解釈できるため、一致するかどうかを考慮する必要があります.

グローバル変数を初期化する必要があるかどうかを確認します.

約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ヒット率

減少

#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

ベクトルと同様に、前後の追加/削除:O(1)

要素がメモリ内で不連続である

フル時に要素を追加し、ベクトルとは異なり、既存の要素

をコピーしません.

#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

バランスツリー構造

キー、値ペア

キーは一意で、繰り返し不可能な値

です.

を挿入するときの自動ソート(デフォルトは昇順)

#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;
}

正規表現

#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;
}

low bound/upper bound,バイナリナビゲーション

が重複していない場合はlow boundで求めます...

冗長時、上限-下限

注意:upper boundはtargetの次の反復器を返します!(オープン)

#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;
}

ダエストラ

は、1つのノードから他のすべてのノードへの最短距離

である.

すべての幹線は自然水でなければなりません.

メッシュアルゴリズムは、非アクセスノードの中で最も短いノードを中心に最短距離を更新する
-最短距離=

更新なし

#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;
}

その他の最短距離アルゴリズム

流水アルゴリズム
-すべての点の最小値を求めることで距離を更新します.
-すべての点間の最小距離を求める(最小距離テーブルが表示される)

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/交差、パラレル/交差
set unionは、set conculationの前に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;
}