[cpp] Code Note

Yujin-Shim·2023년 7월 5일
0

codingtest-cpp

목록 보기
1/7
post-thumbnail

예전에 코딩테스트를 준비하면서
인상적인 함수나 몰랐던 방법들을 볼 때마다 notion에 적어두곤 했는데,
이제 TIL를 velog로 옮기면서 조금씩 옮기고 있다.

(notion에서 내보내기 > markdown 으로 하면 velog에 아주 잘 호환된다.)

Code Note

💡 To master Python & C++
  • Tips
    • for 문에서 len(list)같이 계산이 필요한 것들 loop에 넣으면 시간 복잡도 급 상승, for loop전에 변수로 선언해주고 변수만 넣어주기
    • vector에서는 마지막요소idx로 -1 안됨! v.back() 이용~

Char to int

노트

char c = '1';
int n = c - '0';
// n = 1

이진수

1의 갯수 세기

int n = 10;
int x = __builtin_popcount(n);

//gcc 컴파일러 내장함수 - unsigned int를 받아서 1인 bit의 개수를 리턴
// unsigned int = 32bit -> 시간복잡도 O(32)

priority queue

조건에 맞춰 정렬하고 싶을 때 - 삼성코테예제 중 BFS 쓸때 유용~

// 값을 priority queue에 넣어주면 struct에 선언된 기준대로 정렬해줌!!
#include <queue>

struct standard {
	int x,y,x_cnt, y_cnt;
	bool operator <(const standard& i const{
		if(x == i.x)
		{
			if(y == i.y)
			{
					return x_cnt > i.x_cnt // x값도 y값도 같은 경우, x_cnt가 작은 순서대로 정렬
			} else return y > i.y // 들어온 값들의 x값이 같은 겅우, y가 작은 순서대로 정렬
		}
		else return x < i.x // x가 클수록 앞으로 정렬
	}
};

int main()
{
	priority_queue<standard> qp;
	pq.push({1,2,3,4});
	int x_first = pq.top().x;
}

Tuple

Tuple(3개의 요소 한번에 넣고 싶을때) - 2개는 pair

#include <tuple>
#include <vector>
vector <tuple<int,int,int>> v;

v.push_back({1,2,3});
a = get<0>(v.front());
b = get<1>(v.front());
c = get<2>(v.front());

Sort

Sort

#include <vector>
#include <algorithm>
vector <int> v;

// Vector
// 오름차순
sort(v.begin(), v.end());

// 내림차순
sort(v.begin(),v.end(), greater<>());
sort(v.rbegin(),v.rend());

// Array
sort(arr,arr+5);
# 오름차순
list.sort()

# 내림차순
list.sort(reverse = True)

Vector

Basic functions

#include <vector>
vector <int> v;  // 1d vector
vector <vector<int>> v2; // 2d vector

v.push_back(a); // add a to end of vector
v.emplace_back(a);
v.pop_back(); // delete last element
v.size(); // size of the vector v
v.begin(); // address of first element
v.end(); // address of last element

Vector

min, max, idx

#include <vector>
vector <int> v;

int min = *min_element(v.begin(),v.end());
int max = *max_element(v.begin(),v.end());

int max_idx = max_element(v.begin(),v.end()) - v.begin();
int min_idx = min_element(v.begin(),v.end()) - v.begin();

//그냥 값을 넣어서 구할수도 있다.
int min = min(v[0],v[1]); // 이렇게 !

Vector

Count (개수세기)

#include <vector>
#include <algorithm>
vector <int> v;

// 2가 몇개 있는지 찾고싶을 때
int target = 2; 
int c = count(v.begin(),v.end(),target);

// 2 이하가 몇개인지 찾고싶을 때
int cc = count_if(v.begin(),v.end(), [](int elem){return elem <= 2;});

or
bool cnt (int x)
{
	return (x <= 2); // 진짜 숫자 상수 밖에 안됨, vector[i] 도 넣어봤는데 안됨. 아마 int main 안에서 선언되는게 아니라 그런듯
}
int cc = count_if(v.begin(),v.end(), cnt);

Vector

Vector 값 모두 출력하기

for (auto loop:v)
{
		cout << loop << " ";
}

Vector

특정값 idx 찾기

#include <algorithm>

auto idx = find(v.begin(), v.end(), target);
cout << idx - v.begin()+1; // idx 출력
cout << *idx; // vector의 idx값

// 있으면 
if (idx != v.end())
{
	cout << "Element found : " << *idx;
}
else
{
	cout << "Element Not found";
}

Vector

n번째 idx값 출력하기

vector <int> :: iterator idx = v.begin() + n + 1;
cout << *idx;

Vector

2차원 벡터 입력받기

int n, m; // row, col
vector <vector <int>> v2;

for (int i = 0; i<n; i++)
{
		for (int j = 0; j < m: j++)
		{
				int temp;
				cin >> temp;
				v2[i].push_back(temp);
		}
}

input.txt

Input.txt로 불러오기

리소스파일 폴더에 input.txt 만들어두고

#define LOCAL
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>

int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
}

Vector

String 일부만 추출하기

// substr(start, length)
v.substr(0,v[0].size());

Set (중복x)

Set

#include <set>
set <int> s1;

s1.insert(10);
// 중복 x, 자동 오름차순 정렬
# list to set
# 중복 제거

ls = [1,2,3,4,5,5,5]
ss = set(ls)

Unordered_set

-장점: insert, find, erase =O(1)

-주의: 내부에 랜덤하게 저장됨

순서를 고려하는 경우, 사용 X

  • 시간복잡도가 낮은 이유: 해시함수
  • 입력된 값으로부터 값을 저장할 array의 idx값을 계산 → 값으로부터 idx값을 알 수 있으므로 탐색X

unordered_set find

#include <unordered_set>

unordered_set <int> mm;

if (mm.find(10) != mm.end()){
	// 10 mm안에 있음}

mm.find(x) == mm.end()true면 없는거 (끝까지 탐색했는데 없어서 end idx와 같아지면)

문자열(공백찾기)

isspace

//isspace : 공백이 아니면 0 반환

if (isspace(str) != 0) // 공백일 때
if (isspace(str) == 0) // 공백 아닐 때

문자열

문자열 합치기(list → word)

...
str_list = ['a','b','c','d']
''.join(str_list)

# result = 'abcd'

문자열(대문자, 소문자)

tolower, toupper

#include <cctype>
string str = "HOHO";
for (char& ch:str)
{
		ch = tolower(ch);
}
//-------------------------
string word = "HELLO";
transform(word.begin(), word.end(), word.begin(), ::tolower);
cout<<word<<"\n"; //hello

for(int i=0; i<word.size(); i++) {
    word[i] = ::toupper(word[i]);
}
cout<<word<<"\n"; //HELLO
str = "hoho"
str.upper()
str.lower()

문자열(String to int)

stoi

#include <string>

// string to int
string s = "12345";
int ss = stoi(s);

// int to string
to_string(ss)
s = "12345"
ss = int(s)

Vector Remove / erase

Vector에서 특정값 지우기

#include <algoritm>
#include <vector>

target = 10;
v.erase(remove(v.begin(),v.end(),target));
target = 10
list.remove(target)

Vector

Vector 2개 이어붙이기

// vector x 뒤에 y 붙이기

x.insert(x.end(),y.begin(),y.end());
ans = x + y

Vector sum

Vector / list 값 모두 더하기

#include <numeric>

ans = accumulate(v.begin(), v.end(),0); // 0+요소값 전부
ans = sum(ls)

0개의 댓글