[C++] 코딩 테스트 때 쓸 코드

정말 개인적으로 쓰려고 만들었지만 혹시 보고 싶어하실 수도 있으니 포스팅 해보도록 하겠습니다.

 

1. 에라토스테네스의 체 : 소수 찾기

// arr : 'true' if prime num, 'false' if not
    bool *arr = new bool[n+1];
    for(int i = 2; i < n+1; i++){
        arr[i] = true;
    }

    // 에라토스테네스의 체
    for(int i = 2; i * i <= n; i++){
        if(arr[i]){
            for(int j = i * i; j <= n; j += i)
                arr[j] = false;
        }
    }

 

2. 정렬 후 중복 제거

sort(vect.begin(), vect.end());
auto tmp_ = unique(vect.begin(), vect.end());
vect.erase(tmp_, vect.end())

 

3. 역정렬

sort(order.begin(), order.end(), greater<char>());

 

4. 배열 search

int arr[] = {10, 20, 30, 40};
int *ptr;

ptr = find(arr, arr + 4, 30);
if(ptr != arr + 4){
   // FOUND
   cout << "FOUND, POS: " << *ptr << endl;
} else{
   // NOT FOUND
   cout << "NOT FOUND" << endl;
}

 

5. 벡터 search

vector<int> vec; // consider values are in it
vector<int>::iterator it;

it = find(vec.begin(), vec.end(), 30);
if (it != vec.end())
  std::cout << "FOUND, POS : " << distance(vec.begin(), it) << endl;
else
  std::cout << "NOT FOUND" << endl;

6. 문자열 파싱

#include <sstream>

string answer = "";
string token;
vector<int> tokVec;
    
stringstream split_stream(s);
while(split_stream >> token){
    tokVec.push_back(stoi(token));
}
split_stream.clear();

 

7. Hash table using linked list

class Hash{ 
    int BUCKET; // # of buckets    // No. of buckets
    list<int> *table; // pointer to an array containing buckets
public: 
    Hash(int V); // Constructor
    void insertItem(int x); // inserts a key into hash table
    void deleteItem(int key); // deletes a key from hash table 
    void displayHash(); 
}; 
  
Hash::Hash(int b) { 
    this->BUCKET = b; 
    table = new list<int>[BUCKET]; 
} 
  
void Hash::insertItem(int key) { 
    int index = hashFunction(key); 
    table[index].push_back(key);  
} 
  
void Hash::deleteItem(int key) { 
  int index = hashFunction(key); // get the hash index of key 
  
  // find the key in (inex)th list 
  list <int> :: iterator i; 
  for (i = table[index].begin(); 
           i != table[index].end(); i++) { 
    if (*i == key) 
      break; 
  } 
  
  // if key is found in hash table, remove it 
  if (i != table[index].end()) 
    table[index].erase(i); 
} 
  
// function to display hash table 
void Hash::displayHash() { 
  for (int i = 0; i < BUCKET; i++) { 
    cout << i; 
    for (auto x : table[i]) 
      cout << " --> " << x; 
    cout << endl; 
  } 
} 
  
// Driver program  
int main() 
{ 
  // array that contains keys to be mapped 
  int a[] = {15, 11, 27, 8, 12}; 
  int n = sizeof(a)/sizeof(a[0]); 
  
  // insert the keys into the hash table 
  Hash h(7);   // 7 is count of buckets in 
               // hash table 
  for (int i = 0; i < n; i++)  
    h.insertItem(a[i]);   
  
  // delete 12 from hash table 
  h.deleteItem(12); 
  
  // display the Hash table 
  h.displayHash(); 
  
  return 0; 
} 

8. 이진수로 만들고 합치기

// num -> binary
vector<int> binVec; // binary number saved in order in vector
while(n > 1){
    binVec.push_back(n % 2);
    n = n / 2;
}
binVec.push_back(1);
reverse(binVec.begin(), binVec.end());
    
// binary -> num
for(int i = 0; i < binVec.size(); i++){
    answer += pow(2, i) * binVec[binVec.size() - 1 - i];
}
 

9. 벡터 최대 / 최소 찾기

#include <vector>
#include <algorithm> 

using namespace std;

int main()
{
	vector<int> vec = { 3, 4, 2, 6, 8, 10 };
	int min = *min_element(vec.begin(), vec.end());
	int max = *max_element(vec.begin(), vec.end());

}