C++ 문제해결 Cheat sheet

형변환

• 기본적인 것들
  • int → char 로 변환
    • (char) 257 : 257 아스키 코드 값이 그대로 char 가 됨. 아마 ^였나 ㄱ같은 것이었던듯.
• 값 그대로 바꾸기
  1. int에서 string으로 변경하기

     int data = 100;
     string st = to_string(data)

  2. string 에서 int로 변경하기

     string st = "100";
     int data = stoi(st);

  3. int -> char로 변경 : '0' 더하기

     int data = 9;
     char ch = (char)(data + '0');

sort() 함수

• #include <algorithm> 필요!!!
• sort()
• sort(a, a + 10)
• sort(v.begin(), v.end())
• 내림차순으로 정렬하려면?
  • sort(v.begin(), v.end(), greater());

정수 제한

• #include <climits> 에 선언됨
• 사용법: INT_MAX, INT_MIN, LONG_MIN, LONG_MAX, LLONG_MIN, LLONG_MAX

priority_queue

기본 제공 함수

• push() : 우선순위 큐에 원소를 추가, O(logN)
• pop() : 우선순위 큐에서 top의 원소를 제거, O(logN)
• top() : 우선순위 큐에서 top에 있는 원소를 반환한다.
• empty() : 큐가 비어있으면 true를 반환하고 그렇지 않으면 false를 반환.
• size() : 우선순위 큐의 원소의 수를 반환한다.

내림차순, 오름차순 사용

우선순위 큐는 내림차순 정렬(큰 수가 먼저옴) 이다.

• 오름차순 정렬로 사용하려면?
  priority_queue<int,vector<int>,greater<int>> : 오름차순으로 정렬
• pair 사용할 때 오름차순 정렬:
  priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>> > pq;

사용 예시

pq.push({heights[0][0], {0,0}});
        
while (!pq.empty()) {
    int val = pq.top().first;
    int y = pq.top().second.first;
    int x = pq.top().second.second;
    pq.pop();

queue

기본 제공 함수

• q.size() : 큐 사이즈(원소의 개수)를 리턴
• q.empty() : 큐 사이즈가 0인지 아닌지를 확인
• q.front() : 큐에 가장 먼저 들어간 원소를 리턴
• q.back() : 큐에 가장 나중에 들어간 원소를 리턴
• q.push(val) : 큐의 뒤에 값(val) 추가
• q.pop() : 큐에 가장 먼저 들어간 원소를 삭제
• queue 는 find 가 없음.
• queue 는 clear가 없음

queue 에는 top이 아니라 front였다는걸 까먹음..
queue<pair<int, int>> q 의 원소를 찾아갈땐 q.front().first, q.front().second.. 이런식으로 가야함.

vector

기본 제공 함수

• size() - 원소의 개수를 반환한다.
• swap(vector객체) - 두 벡터의 내용을 교환(교체)한다.
• empty() - 벡터가 비었는지 여부를 반환한다.
• at(index) - index번째 요소에 접근한다.
• front() - 벡터의 첫 번째 원소를 반환한다.
• back() - 벡터의 마지막 원소를 반환한다.
• begin() - 벡터의 첫 번째 원소를 가리킨다.
• end() - 벡터의 마지막 원소를 가리킨다.
• insert(v.begin() + 2, val) - 벡터 v 의 처음 + 2 위치에 val를 삽입한다.

사용 예시

vector<vector<int>> v;
vector<int> tmp;
tmp.push_back(3);
v.push_back(tmp);
tmp.clear();
tmp.push_back(9);
tmp.push_back(20);
v.push_back(tmp);
이런식으로 가야 [3],[9,20]... 이렇게 쌓임.

pair 사용

• vector에서 pair를 사용하여 값을 저장하려고 할때

vector<pair<int, int>> v;
v.push_back({1,2}) // 이렇게 넣고
v[0].first, v[0].second // 이렇게 뺀다.

vector 초기화

1차원 벡터 초기화

// int n = 초기화될 갯수
vector<int> vect(n, 10);

2차원 벡터 초기화

// nm 배열 초기화
vector<vector<int>> vec(n , vector<int> (m, 0));

사용 예시

vector<int> dp;
dp = vector<int>(1000, -1);

vector 복사하기

vector<int> v;
v.assign(tmp);

map

시간복잡도

삽입, 삭제, 찾기 (insert, erase, find), count: O(logN)

기본 제공 함수

• rbegin() 거꾸로 begin 출력 = end 출력
• rend()
• erase(삭제할 key 넣기)

내림차순으로 데이터 넣기

map<int, int, greater<int>> m; // 이렇게 선언하고 넣으면 
// {4, 19}
// {3, 10}
// {-1, 3} 
// ... 이런식으로 들어간다.

데이터 접근

대괄호([,]) 사용하여 value 데이터에 접근할 수 있다.

map<int, int> prices;
prices[key] 하면 value 값이 나옴

반복문 데이터 접근 (first, second)

for (auto iter = m.begin() ; iter != m.end(); iter++)
{
cout << iter->first << " " << iter->second << endl;
}

multiset

기본 제공 함수

• #include <set> 필요! <multiset> 이 아님을 유의!!
• erase()
  • multiset.erase(val) ⇒ 이러면 모든 val 값을 모두 다 삭제함!!!!
  • multiset.erase(iter) 로 지워야 하나만 지워진다. (관련 문제: 253, meeting rooms II)
• insert()

multimap

• #include<map>
• leetcode 한정일수도 있는데, multimap까지 필요한 경우는 잘 없다. 더 쉽게 풀 수 있다는 뜻이다.
• 항상 헷갈리는게 multimap의 특정 키를 for loop 할 수 있다고 생각하는데, 그런기능은 없다.
• map과 다르게 []를 이용하여 insert할 수 없다.
  insert는 m.insert({key, value}) 이렇게 하는것이다.

mm.begin();
mm.end();
mm.rbegin();
mm.rend();
mm.clear();
mm.count(key);
mm.empty();
mm.insert(pair < >);     // pair 객체입니다.
mm.erase(start, end);
mm.find(key);
mm2.swap(mm1);
mm.value_comp();
mm.key_comp();
mm.max_size();
mm.size();