Coding Test Snippet - 코딩테스트 스니펫

0. 알아두면 좋은

#include <bits/stdc++.h>

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

// call by reference (integer variable)
int fn(int* p){
    *p = 33;
}
int a = 1;
fn(&a); // -- 33으로 변경

void fn(vector<int> &v){
    v[1] = 333;
}
vector<int> g = {2, 3, 4, 5};
fn(g); // -- g[1] = 333으로 변경

1. Vector 벡터

1. vector STL

#inclue <vector>

using namespace std;

vector<int> v; // 비어있는 vector 
vector<int> v2(4); // 크기가 4인 vector 
vector<int> v3(5, 2); // 크기가 5인 2로 초기화된 vector
vector<int> v4(v2); // v2를 복사한 벡터

v.assign(5, 2); // 2의 값으로 5개 원소 할당
v.at(2); // 2번째 원소 참조
v[2];
v.front(); // 첫 번째 원소 참조
v.back(); // 마지막 원소 참조
v.clear(); // 모든 원소 제거 size()는 줄어들고 capacity는 그대로
v.push_back(3); // 마지막 원소 뒤에 3 삽입
v.pop_back(); // 마지막 원소 제거
v.begin(); // 첫 번째 원소 가리킴 (Iterator)
v.end(); // 마지막의 다음을 가리킨다. (Iterator)
v.reserve(n); // n개의 원소 저장위치 예약 동적할당
v.resize(n); // 크기 n으로 할당
v.resize(n, 3); // 크기를 n으로 변경하고 size가 더 커졌을 경우인자값 3을 초기화 
v.insert(v.begin() + 2, 3); // 2번째 위치에 3 삽입 
v.insert(v.begin() + 2, 3, 4); // 2번째 위치에 3개의 4 삽입 

2. 이차원 벡터 입력

vector<vector<int>> graph;

for (int i = 0; i <= n; i++) {
	vector<int> v;
	graph.push_back(v);
}

for (int i = 0; i < m; i++) {
	int a, b;
	scanf("%d %d", &a, &b);
	graph[a].push_back(b);
}

// 3 3 3 3 3
// 3 3 3 3 3
// 3 3 3 3 3
vector<vector<int>> vv(3, vector<int>(5, 3));

3. vector sort() (벨로그)

bool comp(const int o1, const int o2){
    return true; // 두 데이터를 바꾸지 않는다.
    return false; // 두 데이터 o1과 o2을 바꾼다. (Swap)
}

// 오름차순 comp()
bool comp(const int o1, const int o2){
    return o1 <= o2;
}

// 내림차순 comp()
bool comp(const int o1, const int o2){
    return o1 > o2;
} 

// condition1이 가장 작거나
// conditinon2가 가장 큰 (condition1이 같은 경우)
// -> 가장 뒤로 가게 (오름차순)

bool comp(const int o1, const int o2){
	if(condition1[o1] == condition1[o2]){
		if(condition2[o1] < condition2[o2]){
			return true;
		}
		else{
			return false;
		}
	}
	else if(condition1[o1] > conditoin1[o2]){
		return true;
	}
	else{
		return false;
	}
}

sort(v.begin(), v.end()); // 오름차순
sort(v.begin(), v.end(), less<int>()); // 오름차순
sort(v.begin(), v.end(), greater<int>()); // 내림차순
sort(v.begin(), v.end(), comp);

이차원 벡터 시계방향 회전

// 행렬 시계방향 회전
vector<vector<int>> clockwiseRotate(vector<vector<int>> v, int count){
    int size = v.size();
    vector<vector<int>> result = v;

    // count 만큼 시계방향 회전
    for(int t = 0; t < count; t++){
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                result[j][size - i - 1] = v[i][j];
            }
        }
        v = result;
    }
    return result;
}

이차원 벡터 반시계방향 회전

// 행렬 반시계방향 회전
vector<vector<int>> counterClockwiseRotate(vector<vector<int>> v, int count){
    int size = v.size();
    vector<vector<int>> result = v;

    // count 만큼 반시계방향 회전
    for(int t = 0; t < count; t++){
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                result[size - j -1][i] = v[i][j];
            }
        }
        v = result;
    }
    return result;
}

2. Stack 스택 (벨로그)

3. queue 큐 (벨로그)

4. priority_queue 우선순위 큐 (벨로그)

priority_queue<int> pq;
priority_queue<int, vector<int>, compare> pq;

// 1. Top이 가장 큰 수 (우선순위가 큰 수일 때)
priority_queue<int, vector<int>, less<int>> pq;

// 2. Top이 가장 작은 수(우선순위가 작은 수일 때)
priority_queue<int, vector<int>, greater<int>> pq;

// 3. 우선순위 재정의하여 사용 (Custom 우선순위)
struct compare{
	bool operator()(int a, int b){
		return a < b; // Top이 가장 작은 수
		// return a > b; // Top이 가장 큰 수
	}
};

struct Data{
	int idx;
	int value;
};

struct Comp{
	bool operator()(const Data& a, const Data& b){
		return a.value > b.value; // value 작은 값이 우선순위
	}
};

priority_queue<int, vector<int>, Comp> pq;

pq.push({idx, value});
pq.top();
pq.pop();

// priority_queue는 clear() 멤버 함수가 존재하지 않는다.
while(!pq.empty()){
	pq.pop();
}

5. Heap 힙 (우선순위 큐 힙 벨로그) (최소힙) (최대힙)

priority_queue<int> pq; // maxHeap (default)
priority_queue<int, vector<int>, less<int>> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

6. Binary Search 이분 탐색

int left = 0;
int right = n;

while(left <= right){
	int mid = (left + right) / 2;
			
	if(data[mid] == target){
		exist = true; // 맞는 logic으로 짜기
		break;
	}
	else if(data[mid] > target){
		right = mid - 1;
	}
	else{
		left = mid + 1;
	}
}

7. Two Pointer 투 포인터

sort(AB.begin(), AB.end()); // 오름차순
sort(CD.begin(), CD.end(), greater<int>); // 내림차순

long long int result = 0;
int ptab = 0, ptcd = 0;

while (ptab < AB.size() && ptcd < CD.size()) {
	int currentAB = AB[ptab];
	int target = -currentAB;

	if (CD[ptcd] == target) {
    	    int ab = 0, cd = 0; // 같은 경우 개수 찾기
            while(AB[ptab] == currentAB && ptab < AB.size()){
                ab++;
                ptab++;
             }
             while(CD[ptcd] == target && ptcd < CD.size()){
                cd++;
                ptcd++;
             }
             result += (long long int) ab * cd;
        }
	else if (CD[ptcd] > target) {
	    ptcd++;
	}
	else {
	    ptab++;
	}
}

8. multiset 멀티셋 중복 Key 값 (벨로그)

// 1. 오름차순 정렬 (default)
multiset<int> ms;
multiset<int, less<int>> ms; 

// 2. 내림차순 정렬
multiset<int, greater<int>> ms;

// 데이터 삽입
ms.insert(50);
ms.insert(50);
ms.insert(10);
ms.insert(80);
ms.insert(80);

// 데이터 삭제
ms.erase(ms.begin()); // 첫번째 요소 삭제
ms.erase(--ms.end()); // 마지막 요소 삭제

// 데이터 접근
multiset<int>::iterator it;
for(it = ms.begin(); it != ms.end(); it++){
	cout << *it;
}

9. unordered_map 해쉬테이블

unordered_map<string, int> u; // key type, value type
u["A"] = 1;
u["B"] = 22;

// unordered_map 접근
for(auto elem : u){
	cout<<"key : "<<elem.first<<" value : "<<elem.second<<endl;
}

// 이차원 value 값
unordered_map<string, vector<int>> u; // key type, value type
vector<int> v;
string key = "abc";

u[key] = v;
u[key].push_back(2);
u[key].push_back(66);

for(int i = 0; i < u[key].size(); i++){
	cout << u[key][i] << " ";
}

10. String

// 문자열 입력
string s;
cin >> s;

// 한 줄 입력
while(getline(cin, s)){
	cout << s << endl;
}

// 문자열 길이
char str[25];
scanf("%s, str); // hello
strlen(str); // 5

// scanf로 string 입력받고 string type으로 만들기
char cstr[1010] = "";
scanf("%s", cstr);

string st(cstr);
cout << st;

// integer -> 문자열로 변환
int num = 10;
cout << to_string(number);

stoi = string to int
stof = string to float
stol = string to long
stoll = string to long long
stod = string to double

// 문자열 탐색
for(auto i : s){
    cout << i << endl
}

// 문자열 교체
string base = "this is a test string.";
string replace = "example 1";

base.replace(9, 5, replace); // 9 ~ (9+5-1) 교체

// 문자열 뒤집기
reverse(s.begin(), s.end());

// 문자열 찾기
string s = "helloll"
cout << s.find("ll") << endl;  // -> 2 ( 첫 시작 위치 인덱스)
cout << s.find("ll", 3) << endl; // -> 5 (3위치부터 검색) 

// 문자열 자르기
cout << s.substr(0, 4) << endl; // -> "hell" (0부터 4개)
cout << s.substr(5) << endl; // -> "ll" (5부터 끝까지)

// 뮨자열 교체
cout << s.replace(3, 2, "rr") << endl; // s 문자열 변경됨 
cout << s << endl;

// 문자열 대문자로 
for(int i = 0; i < s.length(); i++){
    s[i] = toupper(s[i]);
}
cout << s << endl;

// 문자열 소문자로 
for(int i = 0; i < s.length(); i++){
    s[i] = tolower(s[i]);
}
cout << s << endl;

// 문자열 공백 제거
string str = " jo hye  jeong ";
str.erase(remove(str.begin(), str.end(), ' '), str.end());
cout << str << endl;

// string 구분자로 자르기
vector<string> split(string str, char delimiter) {
    vector<string> answer;
    int prev = 0, current = str.find(delimiter);

    while (current != -1) {
    	string tmp = str.substr(prev, current - prev);
        answer.push_back(tmp);
      
        prev = current + 1;
        current = str.find(delimiter, prev);
    }
    answer.push_back(str.substr(prev, current - prev));

    return answer;
}

int main(){
	vector<string> subS = split(s, ' ');
}

9. 최대공약수 (유클리드호제법) (벨로그)

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a; //(b가 0이 아니면 : b가 0이면)
}

int lcm(int a, int b) {
  return (a * b) / gcd(a, b);
}

10. 에라토스테네스의 체

bool isPrime[MAX];
vector<int> prime;
	
for (int i = 0; i < MAX; i++) {
	isPrime[i] = true;
}

for (int i = 2; i < MAX; i++) {
	if (isPrime[i]) {
		prime.push_back(i);
		for(int j = 2 * i; j < MAX; j += i) {
			isPrime[j] = false;
		}
	}
}

11. 트리 순회

12. Union Find 서로소 집합

vector<int> parent;

void init() {
	for (int i = 0; i <= n; i++) {
		parent.push_back(i);
	}
}

int find(int a) {
	if (parent[a] != a)
		parent[a] = find(parent[a]);
	return parent[a];
}

void unionF(int a, int b) {
	int pa = find(a);
	int pb = find(b);
	parent[pb] = pa;
}

if(find(a) == find(b)){
	// 같은 집합
}

Topological Sort 위상 정렬 (벨로그)

queue<int> q;

for (int i = 1; i <= n; i++) {
	if (student[i] == 0) {
		q.push(i);
	}
}

while (!q.empty()) {
	int front = q.front();
	q.pop();
		printf("%d ", front);
		for (int i = 0; i < graph[front].size(); i++) {
		if (--student[graph[front][i]] == 0) {
			q.push(graph[front][i]);
		}
	}
}

Kruskal's Algorithm 크루스칼 알고리즘 - 최소 스패닝 트리(MST) (벨로그)

struct Edge{
	int nodeA;
	int nodeB;
	int weight;
};

struct Comp{
	bool operator()(const Edge& A, const Edge& B){
		return A.weight > B.weight;
	}
};

vector<int> parent;

int find(int node){
	if(node == parent[node]) return node;
	else return find(parent[node]);
}

void unionF(int a, int b){
	int pA = find(a);
	int pB = find(b);
	parent[pA] = pB;
}

// main
priority_queue<Edge, vector<Edge>, Comp> edges;
	
int edge = 0;
int result = 0;

for(int i = 0; i <= v; i++){
	parent.push_back(i); // 초기화
}

for(int i = 0; i < e; i++){
	int a, b, w;
	scanf("%d %d %d", &a, &b, &w); // a -> b 간선 가중치 w
	edges.push({a, b, w});
}
	
while(edge < v - 1 || !edges.empty()){ // 간선 개수 v-1개
	Edge minE = edges.top();
	edges.pop();
	
	if(find(minE.nodeA) != find(minE.nodeB)){
		unionF(minE.nodeA, minE.nodeB);
		result += minE.weight;
		edge++;
	}
}

Dijstra Algorithm (다익스트라 알고리즘) (벨로그)

특정한 하나의 정점에서 모든 정점으로의 최소 경로 (단, 음의 간선은 없다)

struct Edge{
	int id;
	int cost;
};

struct Comp{
	bool operator()(const Edge& a, const Edge& b){
		return a.cost > b.cost;
	}
};

vector<vector<Edge>> adjList;
vector<int> dist;

void dijkstra(int start){
	priority_queue<Edge, vector<Edge>, Comp> pq;
	
	dist[start] = 0;
	pq.push({start, dist[start]});
	
	while(!pq.empty()){
		Edge now = pq.top();
		pq.pop();
		
		if(dist[now.id] < now.cost) continue;
		
		int size = adjList[now.id].size();
		for(int i = 0; i < size; i++){
			Edge next = adjList[now.id][i];
			
			if(dist[next.id] > now.cost + next.cost){
				dist[next.id] = now.cost + next.cost;
				pq.push({next.id, dist[next.id]});
			}
		}
	}
}

플로이드 워셜 알고리즘 (최단 경로)

모든 정점에서 모든 정점으로의 최단 경로

const int INF = 1E9;

int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	
	vector<vector<int>> graph(n+1);
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			if(i == j) graph[i].push_back(0); // 대각선 0
			else graph[i].push_back(INF); // INF로 초기화
		}
	}
	
	for(int j = 0; j < m; j++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		graph[a][b] = c; // (양방향일 떄는 각각 설정)
	}
	
	for(int k = 1; k <= n; k++){
		for(int a = 1; a <= n; a++){
			for(int b = 1; b <= n; b++){
				graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
			}
		}
	}
	return 0;
}

DFS

void dfs(vector<vector<int>> &graph, int node, vector<bool> &visite	
	visited[node] = true;
	printf("%d\n", node);
	
	for(int i = 0; i < graph[node].size(); i++){
		int idx = graph[node][i];
		if(!visited[idx]){
			dfs(graph, idx, visited);
		}
	}
}

int main(){
	vector<vector<int>> graph = {
		{},
		{2, 3, 7},
		{1, 7},
		{1, 4, 5},
		{3, 5},
		{3, 4},
		{7},
		{2, 6, 8},
		{1, 7}
	};
	
	vector<bool> visited(graph.size(), false);	
	dfs(graph, 1, visited);
   
    return 0;
}

BFS

void bfs(vector<vector<int>> &graph, int node, vector<bool> &visited){
	visited[node] = true;
	queue<int> q;
	q.push(node);
	
	while(!q.empty()){
		int top = q.front();
		q.pop();
		
		printf("%d\n", top);
		
		for(int i = 0; i < graph[top].size(); i++){
			int idx = graph[top][i];
			if(!visited[idx]){
				q.push(idx);
				visited[idx] = true;
			}
		}		
	}
}

int main(){
	vector<vector<int>> graph = {
		{},
		{2, 3, 8},
		{1, 7},
		{1, 4, 5},
		{3, 5},
		{3, 4},
		{7},
		{2, 6, 8},
		{1, 7}
	};

	vector<bool> visited(graph.size(), false);
	bfs(graph, 1, visited);

	return 0;
}

상하좌우 움직이기 (완전 탐색 & DFS)

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void ice(vector<vector<int>> &graph, int y, int x){
	if(graph[y][x] == 1) return;

	graph[y][x] = 1;

    for(int i = 0; i < 4; i++){
		ice(graph, y + dy[i], x + dx[i]);
	}
}

이차원 벡터 초기화 (상하좌우 blocking)

int n, m;
scanf("%d %d", &n, &m);
	
vector<vector<int>> data(n+2);
		
for(int i = 0; i < n+2; i++){
	data[i].resize(m+2, 1); // 0 또는 1 조건에 맞게
}
	
for(int i = 1; i <= n; i++){
	for(int j = 1; j <= m; j++){
		int x;
		scanf("%1d", &x);
		data[i][j] = x;
	}
} 

이차원 벡터 BFS (pair / make_pair)

void mapBFS(vector<vector<int>> &graph, vector<vector<bool>> &visited, int y, int x){
	visited[y][x] = true;
	
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));
	
	while(!q.empty()){
		pair<int, int> front = q.front();
		q.pop();
		
		int currY = front.first;
		int currX = front.second;
		
		for(int i = 0; i < 4; i++){
			int nextY = currY + dy[i];
			int nextX = currX + dx[i];
			
			if(!visited[nextY][nextX]){
				q.push(make_pair(nextY, nextX));
				graph[nextY][nextX] = graph[currY][currX] + 1;
				visited[nextY][nextX] = true;
			}
		}
	}
}

int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	
	vector<vector<int>> data(n+2);
	vector<vector<bool>> visited(n+2);
		
	for(int i = 0; i < n+2; i++){
		data[i].resize(m+2, 1);	
		visited[i].resize(m+2, true);
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			int x;
			scanf("%1d", &x);
			data[i][j] = x;
			visited[i][j] = false;
		}
	} 
	
	mapBFS(data, visited, 1, 1);
	printf("%d", data[n][m]);

	return 0;
}

약수의 개수 구하기

int number = 12, divCount = 0;
for(int i = 1; i * i <= number; i++){
	if(number % i == 0){
		divCount++;
		if(i * i < number){
			divCount++;
  		}
	}
}

정규 표현식

✔ 헤더

#include <regex> // c +11 부터 사용 가능

✔ 정규식 생성

// (regex 인스턴스를 생성해 생성자에게 검사할 형식을 인수로 넘겨준다.)
regex re("~~~~"); // 매개변수로 검사 형식 넘겨줌

✔ Syntax (문법)

^x : '^'는 문자열 시작을 의미 (x로 시작한다.)
x$ : '$'는 문자열 종료를 의미 (x로 끝난다.)
.x : '.'은 개행문자(\n)를 제외한 모든 문자를 의미
x+ : '+'는 1회 이상 반복을 의미 ({1, }와 같음)
x* : '*'은 0회 이상 반복을 의미({0, }와 같음)
x? : '?'는 0 or 1개의 문자 매칭을 의미 ({0, 1})
x|y : '|' 는 or을 의미 (x또는 y)
(x) : '()'는 그룹을 표현 ex) (abc){3} ⇒ abcabcabc 검출
x{n} : '{}'는 반복을 의미 x가 n번 반복된다.
x{n, } : x가 n번 이상 반복된다.
x{n, m} : x가 n번 ~ m번 사이 반복된다.
[xy] : '[]'는 x or y를 찾는다는 의미. ([a-z0-9] ⇒ 소문자 or 숫자)
[^xy] : '[^]'은 not을 의미. (xy 제외하고 찾는다.)

\\d : 숫자 (digit)
\\D : 숫자 제외 (not digit)
\\s : 공백 (space)
\\S : 공백 제외 (not space)
\\t : tab
\\w : 알파벳 (대, 소문자), 숫자 [A-Za-z0-9]
\\W : \w 제외한 특수문자

✔ Code

프로그래머스 문제 참고

for(int i = 0; i < queries.size(); i++){
        string reg = "";
       
        int qmCount = 0;
        for(int j = 0; j < queries[i].length(); j++){
            if(queries[i][j] == '?'){
                qmCount ++;
            }
            else{
                if(qmCount > 0){
                    reg += "\\w{" + to_string(qmCount) + "}";
                    qmCount = 0;
                }
                reg += queries[i][j];
            }
        }
        if(qmCount > 0){
            reg += "\\w{" + to_string(qmCount) + "}";
        }
       
        regex re(reg);
       
        int result = 0;
        for(int j = 0; j < words.size(); j++){
            if(regex_match(words[j], re)){
                result ++;
            }
        }
        answer.push_back(result);
    }