SujinLee

memoization

  • Memoization is a technique that speeds up program execution by eliminating duplicate execution of the same calculation by storing previously calculated values in memory when a computer program needs to repeat the same calculations.
  • Example
    • binomial coefficient
    • nCr = n-1Cr + n-1Cr-1
    • nCn == nC0 : 1
      • Number of cases of selecting all n out of n
      • Number of cases of selecting none of n
        • Since above there is only 1 case for each, nCn and nC0 have a value of 1.
    • Utilize the result of the combination already calculated so that it is not redunduntly calculated twice
  • binomial coefficient 
#include<bits/stdc++.h>
using namespace std;

int memoi[22][22];

int dfs(int n, int r) {
	if(memoi[n][r]) return memoi[n][r];
	if(n == r || r == 0) return 1;
	else return memoi[n][r] = dfs(n-1, r) + dfs(n-1, r-1); // dfs(n-1, r) + dfs(n-1, r-1) 怨꾩궛??寃곌낵瑜?memoi[n][r] ???€?낇븯怨? memoi[n][r] ??return 
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	freopen("input.txt", "rt", stdin);
	
	int n, r;
	cin >> n >> r;
	
	// nCr = n-1Cr + n-1Cr-1
	cout << dfs(n, r);	

 	return 0;
}
SujinLee

C++ Class Inheritance

  • LocalDataBaseImpl
// FeatureHandlerBase.h
class FeatureHandlerBase
{
public:
  virtual void setFeatureGenericResponsible(FeatureGenericResponsible* featureResponsible) = 0;
}

//TackHandler.h
class TaskHandler: public FeatureHandlerBase
{
    // Parent Class : FeatureHandlerBase
    // Child Class : TaskHandler
  void setFeatureGenericResponsible(FeatureGenericResponsible* featureResponsible) override;
}

// TaskHandler.cc
void TaskHandler::setFeatureGenericResponsible(FeatureGenericResponsible* featureResponsible)
{
  m_featureResponsible = featureResponsible; // featureResponsible will be set as LocalDataBaseImpl
  m_LocalDataData = m_featureResponsible->getData();
}

// LocalDataBaseImpl.h
class LocalDataBaseImpl: public LocalData,
                         public FeatureGenericResponsible,
{
    // Parent Class : LocalData, FeatureGenericResponsible
    // Child Class : LocalDataBaseImpl
}

// LocalDataBaseImpl.cc
void LocalDataBaseImpl::initFeatureHandler(void)
{
  FeatureHandlerBase* taskHandler = new TaskHandler(); // create TaskHandler object
  taskHandler->setFeatureGenericResponsible(static_cast<FeatureGenericResponsible*>(this)); // this : LocalDataBaseImpl object
  m_featureHandlerMap.insert(std::pair<FeatureTypeE, FeatureHandlerBase*>(FEAT_TYPE_AAA, taskHandler));
}

virtual function

  • A virtual function allows derived classes to replace the implementation provided by the base class.

static_case(obj)

Change Object type

this

  • The this pointer holds the address of current object
SujinLee

What is reserve()

  • reserve(10) reserves memory so you can e.g. push_back(10) elements without having a reallocation.

void reserve (size_type n);

  • Request a change in capacity

  • Requests that the vector capacity be at least enough to contain n elements.

  • If n is greater than the current vector capacity, the function causes the container to reallocate its storage increasing its capacity to n (or greater).

  • In all other cases, the function call does not cause a reallocation and the vector capacity is not affected.

  • This function has no effect on the vector size and cannot alter its elements.

resize()

  • The resize() method (and passing argument to constructor is equivalent to that) will insert or delete appropriate number of elements to the vector to make it given size (it has optional second argument to specify their value). It will affect the size(), iteration will go over all those elements, push_back will insert after them and you can directly access them using the operator[].

  • The reserve() method only allocates memory, but leaves it uninitialized. It only affects capacity(), but size() will be unchanged. There is no value for the objects, because nothing is added to the vector. If you then insert the elements, no reallocation will happen, because it was done in advance, but that’s the only effect.

reserve() and push_back() is faster than resize()

std::vector reserve() and push_back() is faster than resize() and array index, why?

Example

// Example program
#include <iostream>
#include <vector>
#include <string>

int main()
{
    std::vector<int> v1;
    v1.resize(10); //allocation + instance creation
    std::cout << "v1.size(): " <<v1.size()<< std::endl;
    std::cout <<(v1.size() == 10)<< std::endl;   //prints 1
    std::cout <<(v1.capacity()==10)<< std::endl; //prints 1
    for(auto x : v1) {
        std::cout << x << std::endl;
    }
    
    std::vector<int> v2;
    v2.reserve(10); //only allocation    
    std::cout << "v2.size(): " <<v2.size()<< std::endl;
    std::cout <<(v2.size() == 10)<< std::endl;   //prints 0
    std::cout <<(v2.capacity()==10)<< std::endl; //prints 1
    for(auto x : v2) {
        std::cout << x << std::endl;
    }
    for(int i = 0; i < 10; i++) {
        v2.push_back(i);
    }
    std::cout << "v2.size(): " <<v2.size()<< std::endl;
    std::cout <<(v2.size() == 10)<< std::endl;   //prints 1
    std::cout <<(v2.capacity()==10)<< std::endl; //prints 1
    for(auto x : v2) {
        std::cout << x << std::endl;
    }
}

output

v1.size(): 10
1
1
0
0
0
0
0
0
0
0
0
0
v2.size(): 0
0
1
v2.size(): 10
1
1
0
1
2
3
4
5
6
7
8
9