c++ 문법

메모리 초기화

#include <string.h>

bool arr1[1001];
memset(arr1, false, sizeof(check));

int arr2[1001];
memset(arr2, 0, sizeof(check));

vector사용법

• 1차원 vector

#include <vector>                    
vector<int> v;                       // int타입 벡터 생성
vector<int> v = { 1, 2, 3 };         // int형 백터 생성 후 1, 2, 3 으로 초기화
v.push_back(2);                      // v[3]부터 값 추가됨

vector<int> v(10);                   // 10개의 원소를 0으로 초기화
v.push_back(2);                      // v[10]부터 값 추가됨

vector<int> v(10, 3);                // 5개의 원소를 3으로 초기화
v.push_back(2);                      // v[10]부터 값 추가됨

• 2차원 vector

#include <vector>                    
vector<int> v[10];                   // int타입 벡터 배열(크기 : 10) 생성
// v[0] ~ v[9]까지만 사용 가능
vector<int> v[] = {{ 1, 2}, {3, 4}}; // v[0] ~ v[1]까지만 사용 가능

vector<vector<int>> v;               // 2차원 백터 생성(행과 열 모두 가변)
vector<int> v2;
v.push_back(v2);

• vector 삭제

v.pop_back();                        // 마지막에 넣은 값 제거
v.erase(vec.begin()+10);             // index 10의 값을 제거
v.erase(vec.begin(), vec.begin()+5); // index 0~5의 값을 제거
v.clear();                           //모든 값 제거

Hash Map(Unordered_map)

#include <unordered_map>

unordered_map<string, int> hash;
unordered_map<string, int>::iterator iter;

hash.insert({ "apple", 1 });
hash.insert({ "banana", 1 });

iter = hash.find("banana");
if(iter != hash.end()) {
	cout << "key: " << iter->first << "value: " << iter->second;
}

unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다.
이에 비해 map은 binary-search Tree로 탐색 시간이 O(log n)이다. 정렬이 필요없으며, key-value쌍으로 값을 저장해야하고, 탐색이 주를 이룰때 많이 사용한다.

string사용법

• 특정 문자열 찾기 str.find(”bcd”) “bcd”가 문자열에 있는지 확인 있다면 해당 부분의 첫번째 index반환

  #include <string>
  string s = "abcd";
  
  int index = s.find("bcd");

  
  
• 문자열 자르기 str.substr(index, number) 자를 index부터 자를 개수

  #include <string>
  string s = "1234";
  
  string a = s.substr(0,2); // 12
  string b = s.substr(2,2); // 34

  
  

pair/tuple

• pair (두 쌍을 저장하고 싶을 때)

#include <vector>

vector<pair<int, int>> v;

v.push_back(make_pair(1, 2));
v.push_back({ 1, 2 });

int fir = v[0].first;
int sec = v[0].second;

• tuple (세 쌍을 저장하고 싶을 때)

#include <vector>
#include <tuple>

vector<pair<int, int>> v;

v.push_back(make_tuple(1, 2, 3));
v.push_back({ 1, 2, 3 });

int fir = get<0>(v[0]);
int sec = get<1>(v[0]);
int thr = get<2>(v[0]);

우선순위 큐

#include <queue>
priority_queue<int> pq;

pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);

while(!pq.empty()) {
	cout << pq.top() << " ";
	pq.pop();
}
// 4 3 2 1

priority queue는 기본적으로 내림차순으로 정렬된다.

#include <queue>
priority_queue<int, vector<int>, greater<int>> pq;

pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);

while(!pq.empty()) {
	cout << pq.top() << " ";
	pq.pop();
}
// 1 2 3 4

오름차순으로 정렬하기

#include <queue>
priority_queue<pair<int ,int>> pq;

pq.push({ 1, 2 });
pq.push({ 3, 4 });
pq.push({ 5, 6 });
pq.push({ 7, 8 });

while(!pq.empty()) {
	cout << pq.top().first << " " << pq.top().second << "\n";
	pq.pop();
}
// 7 8
// 5 6
// 3 4 
// 1 2

pair형태로 저장하면 첫 번째 인자 기준 내림차순으로 정렬되고,

첫 번째 인자가 같다면 두 번째 인자 기준으로 정렬된다.

#include <queue>
priority_queue<pair<int ,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

pq.push({ 1, 2 });
pq.push({ 3, 4 });
pq.push({ 5, 6 });
pq.push({ 7, 8 });

while(!pq.empty()) {
	cout << pq.top().first << " " << pq.top().second << "\n";
	pq.pop();
}
// 1 2
// 3 4
// 5 6 
// 7 8

pair형태로 오름차순 정렬하기

오버플로우

가끔 답을 n으로 나눈 값을 구하라는 문제가 있다.

보통이면 그냥 n으로 나누면 되지만, 계속해서 값을 저장해야하는 dp문제의 경우 오버 플로우가 발생할 수 있다.

for(int i=3; i <= n; i++ ) {
    dp[i] = (dp[i-1] + dp[i-2]);
}

전수와 전전수를 더하여 dp배열에 저장하는 문제였다.
답을 10007로 나누어 답을 내는 문제였는데, 최대범위가 1000이라 dp[1000]을 계산해도 값이 잘 나오길래 10007을 나눈 값을 그대로 제출했더니 틀렸다. 오버플로우가 발생한 것이다.
아니 그럼 dp[1000]은 나온 것인가? 사실 나온 값보다 훨씬 큰 값인데 잘려나온 것이였다.
이런 경우 dp배열의 값을 전부 출력해보시면 바로 알수 있다.
dp[71]이 약 15억, dp[70]이 약 7억이여서 72부터 71의 결과 + 70의 결과를 더해야 해서 23억이 나오고 int 범위인 2^31 - 1를 초과하게 되어 오버플로우가 나 음수로 나오는것을 확인할수 있다.
이런식으로 계속 오버플로우가 나서 1000을 입력했을 때에는 그냥 우연히 양수가 나와 오버플로우가 안 일어난것처럼 보인것 뿐 단순히 우연일 뿐이였다.
dp문제이고 값을 n으로 나누라는 문제는 오버플로우를 항상 염두해두고 문제를 풀자

백준 11726 - 2xn 타일링