시험 전, 명심할 사항

---

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