코딩도사의 코드정리

template <typename Node>
class CircularQueue
{
private:
    Node* node; // 노드 배열
    int capacity; // 큐의 용량
    int front; // 전단의 인덱스
    int rear; // 후단의 인덱스
public:
    CircularQueue(int capacity)
    {
        this->capacity = capacity + 1; // 노드 배열의 크기는 실제 용량에서 1을 더한 크기 (더미 공간 때문)
        node = new Node[this->capacity]; // Node 구조체 capacity + 1개를 메모리 공간에 할당한다
        front = 0; rear = 0; // 전단과 후단의 초기화
    }
    
    ~CircularQueue()
    {
        delete []node; // 노드 배열 소멸
    }
    void clear()
    {
        front = rear = 0;
    }
    void enqueue(const Node& data)
    {
        int pos; // 데이터가 들어갈 인덱스
        pos = rear;
        rear = (rear + 1) % (capacity);
        node[pos] = data; // pos 번째의 노드의 데이터에 data를 대입한다
    }
    Node dequeue() {
        int pos = front; // pos에 전단의 인덱스 대입
        front = (front + 1) % capacity;
        return node[pos]; // 제외되는 데이터를 반환한다
    }
    int getSize() {
        if (front <= rear) // 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작다면
            return rear - front; // 후단의 인덱스에서 전단의 인덱스를 뺀값을 반환한다
        else // 전단의 인덱스가 후단의 인덱스보다 크다면
            return capacity - front + rear; // 용량에서 전단의 인덱스를 뺀 뒤에 후단의 인덱스를 더한 값을 반환한다
    }
    bool isEmpty() {
        return front == rear; // 전단의 인덱스와 후단의 인덱스가 같을 경우 true, 아니면 false
    }
    bool isFull() {
        return front == (rear + 1) % capacity;
    }
    int getRear() { return rear; }
    int getFront() { return front; }
    vector<Node> getTotalData()
    {
        int tempFront = front;
        vector<Node> T;
        while(tempFront != rear)
        {
            T.push_back(node[tempFront]);
            tempFront = (tempFront + 1) % capacity;
        }
        return T;
    }

    //  void show()
    //  {
    //      int tempFront = front;
    //      while(tempFront != rear)
    //      {
    //          cout << node[tempFront].data << "/";
    //
    //          tempFront = (tempFront + 1) % capacity;
    //      }
    //      cout << endl;
    //  }
};

일반적으로 new/delete 를 통해서 메모리를 할당하는것은 비용을 발생시키고

보기에 위험해 보입니다.

C/C++ 에선 메모리를 할당 하기 위해서 시스템 콜(OS 내부 함수를 요청)을 해야만 하는데 이는 생각보다 큰 비용을 발생 시킵니다. 그래서 할당을 미리 해놓고 꺼내오고 해제된 메모리를 다시 쓰는 방식으로 재활용을 해야하는데, 라이브러리를 잘 짜기가 힘이 듭니다.

boost 로 해결할 수 있습니다.

#include <iostream>
#include <boost/pool/pool.hpp>
#include <boost/pool/object_pool.hpp>
using namespace std;


struct SomeObject
{
    SomeObject()  { static int no=0; cout << "SomeObject() :" << (m_no=++no) << endl; }
    ~SomeObject() { cout << "~SomeObject():" << m_no << endl; }
    int m_no;
};

int main()
{
    {
        // sizeof(int) 바이트 사용
        boost::pool<> p( sizeof(int) );
        int* x = (int*)p.malloc();
        int* y = (int*)p.malloc();
        int* z = (int*)p.malloc();
        *x = 10;
        p.free(z); // 명시적 free

        // free 명시적안해도 알아서 해제됨
    }

    {
        // SomeObject 객체
        boost::object_pool<SomeObject> p;
        SomeObject* x = p.construct();
        SomeObject* y = p.construct();
        SomeObject* z = p.construct();
        p.destroy(y);// 명시적 해제

        // destroy 명시적으로 해제 안해도 알아서 됨.
    }

    return 0;
}

,

n2461.pdf

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <limits>
using namespace std;


#ifdef mycom
ifstream fin("input");
#else
#define fin cin
#endif

vector<int> v;
vector<int> orders;
int N, P, R;

unsigned long long counter=0;
void back(int order)
{
 if(v.size() == orders.size())
 {
  vector<int> arr;
  for(int i=0; i<orders.size(); i++)
  {
   arr.push_back(v[orders[i]]);
  }
  int myp, myr;
  myp = myr = 0;
  for(int i=0; i<arr.size(); i++)
  {
   bool allsmall = true;
   for(int j=0; j<=i; j++)
   {
    if(arr[j] > arr[i])
    {
     allsmall = false;
     break;
    }
   }

   if(allsmall) // arr[i] 가 leftable 하다
   {
    myp++;
   }
  }
  if(myp != P)
   return;
  for(int i=arr.size()-1; i>=0; i--)
  {
   bool allsmall = true;
   for(int j=arr.size()-1; j>i; j--)
   {
    if(arr[j] > arr[i])
    {
     allsmall = false;
     break;
    }
   }

   if(allsmall) // arr[i] 가 rightable 하다
   {
    myr++;
   }
  }
  if(myr != R)
   return;

  counter++;

 }
 else
 {
  for(int i=0; i<v.size(); i++)
  {
   if( find(orders.begin(), orders.end(), i) == orders.end() )
   {
    vector<int> arr;
    for(int i=0; i<orders.size(); i++)
    {
     arr.push_back(v[orders[i]]);
    }
    int myp, myr;
    myp = myr = 0;
    for(int i=0; i<arr.size(); i++)
    {
     bool allsmall = true;
     for(int j=0; j<=i; j++)
     {
      if(arr[j] > arr[i])
      {
       allsmall = false;
       break;
      }
     }

     if(allsmall) // arr[i] 가 leftable 하다
     {
      myp++;
     }
    }
    if(myp > P)
     return;
    orders.push_back(i);
    back(i);
    orders.pop_back();
   }
  }
 }
}

int main()
{
 int mycase;
 fin >> mycase;

 while(fin >> N >> P >> R)
 {
  v.clear();
  for(int i=1; i<=N; i++)
  {
   v.push_back(i); 
  }
  counter = 0;
  back(0);
  cout << counter << endl;
 }

 

 

 return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <limits>
using namespace std;


#ifdef mycom
ifstream fin("input");
#else
#define fin cin
#endif
char chess[100][100] = {0,};
int n, k;
long long total = 0;
bool possible(int y, int x)
{
 int newy = y;
 int newx = x;
 for( ; newy >= 0 && newx >= 0; newy--, newx--)
 {
  if(chess[newy][newx] == true)
  {
   return false;
  }
 }
 newy = y;
 newx = x;
 for( ; newy < n && newx < n; newy++, newx++)
 {
  if(chess[newy][newx] == true)
  {
   return false;
  }
 }
 newy = y;
 newx = x;
 for( ; newy < n && newx >= 0; newy++, newx--)
 {
  if(chess[newy][newx] == true)
  {
   return false;
  }
 }
 newy = y;
 newx = x;
 for( ; newy >= 0 && newx < n; newy--, newx++)
 {
  if(chess[newy][newx] == true)
  {
   return false;
  }
 }
 return true;
}

inline bool sizecompare(int _y, int _x, int __y, int __x)
{
 //_ 가 크면 true;
 if(_y != __y)
  return _y > __y;
 else if(_y == __y)
 {
  return _x > __x;
 }
}
void back(int selcount, int lasty, int lastx)
{
 if(selcount == k)
 {
  total++;
 }
 else
 {
  for(int y=0; y<n; y++)
  {
   for(int x=0; x<n; x++)
   {    
    if(sizecompare(y, x, lasty, lastx) && possible(y, x))
    {
     chess[y][x] = true;
     back(selcount+1, y, x);
     chess[y][x] = false;
    }
   }
  }
 }
}

int main()
{
 bool bfirst = true;
 while(fin >> n >> k && n != 0 && k != 0)
 {
  if(bfirst != true)
  {
   cout << endl;
  }
  bfirst = false;
  total = 0;
  back(0, -1, 0);
  cout << total;
 }
 return 0;
}

vector<int> v;
vector<char> select;
void back(int order)
{
 if(select.size() == v.size())
 {
  for(int i=0; i<select.size(); i++)
  {
    cout << v[select[i]] << ", ";
  }
  cout << endl;
 }
 else
 {
  for(int i=0; i<v.size(); i++)
  {
   if(find(select.begin(), select.end(), i) == select.end())
   {
    select.push_back(i);
    back(i);
    select.pop_back();
   }
  }
 }
}
int main()
{
 int arr[] = {1,2,3};
 v.assign(arr, arr+3);

 back(-1);
 return 0;
}

vector<int> v;
vector<char> select;
void back(bool sel)
{
 if(select.size() == v.size())
 {
  for(int i=0; i<v.size(); i++)
  {
   if(select[i] == true)
    cout << v[i] << ", ";
  }
  cout << endl;
 }
 else
 {
  select.push_back(true);
  back(true);
  select.pop_back();

  select.push_back(false);
  back(false);
  select.pop_back();
 }
}
int main()
{
 int arr[] = {1,2,3};
 v.assign(arr, arr+3);

 back(0);
 return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <limits>
#include <ctime>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
using namespace std;

#ifdef mycom
ifstream fin("input");
#else
#define fin cin
#endif

class team
{
public:
 int score;
 int wincounter;
 int goaldiff;
 int manygoal;
 int gamecounter;
 string teamname;

 ////////////
 int drawcounter;
 int losecounter;
 int sibalgoal;
 team() { 
  score = 0;
  wincounter = 0;
  goaldiff = 0;
  manygoal = 0;
  gamecounter = 0;
  drawcounter=0;
  losecounter=0;
  sibalgoal=0;
 }
 
 bool operator<(const team& t) const
 {
  if(this->score == t.score)
  {
   if(this->wincounter == t.wincounter)
   {
    if(this->goaldiff == t.goaldiff)
    {
     if(this->manygoal == t.manygoal)
     {
      if(this->gamecounter == t.gamecounter)
      {
       char ateam[100];
       char bteam[100];
       strcpy(ateam, teamname.c_str());
       strcpy(bteam, t.teamname.c_str());
       for(int i=0; i<strlen(ateam); i++)
        ateam[i] = toupper(ateam[i]);
       for(int i=0; i<strlen(bteam); i++)
        bteam[i] = toupper(bteam[i]);
       string a = ateam;
       string b = bteam;
       return a > b;
      }
      else
      {
       return this->gamecounter > t.gamecounter;
      }
     }
     else
     {
      return this->manygoal < t.manygoal;
     }
    }
    else
    {
     return this->goaldiff < t.goaldiff;
    }
   }
   else
   {
    return this->wincounter < t.wincounter;
   }
  }
  else
  {
   return this->score < t.score;
  }
 }
};


int main()
{
 int N;
 
 fin >> N;
 fin.ignore(1024, '\n');
 for(int n=1; n<=N; n++)
 {
  int T;
  
  string tonorname;
  char temptonorname[1024];
  
  fin.getline(temptonorname, 1024);
  tonorname = temptonorname;
  fin >> T;
  fin.ignore(1024, '\n');
  vector<team> teams;
  for(int j=1; j<=T; j++)
  {
   char temp[1024];
   fin.getline(temp, 1024);
   team tempteam;
   tempteam.teamname = temp;
   teams.push_back(tempteam);
  }

  int G;
  fin >> G;
  fin.ignore(1024, '\n');
  for(int g=1; g<=G; g++)
  {
   char temp[1024];
   char* p;
   
   int Ascore, Bscore;
   string Aname;
   string Bname;
   fin.getline(temp, 1024);
   p = strtok(temp, "#");
   Aname = p;
   p = strtok(0, "@");
   Ascore = atoi(p);
   p = strtok(0, "#");
   Bscore = atoi(p);
   p = strtok(0, "#");
   Bname = p;
   for(vector<team>::iterator iter = teams.begin(); iter != teams.end(); ++iter)
   {
    if((*iter).teamname == Aname)
    {
     if(Ascore > Bscore)
     {
      iter->score += 3;
      iter->wincounter++;
     }
     else if(Ascore == Bscore)
     {
      iter->drawcounter++;
      iter->score += 1;
     }
     else
      iter->losecounter++;
     iter->sibalgoal += Bscore;
     iter->manygoal += Ascore;
     iter->gamecounter++;
     iter->goaldiff += Ascore - Bscore;
    }
    else if( (*iter).teamname == Bname)
    {
     if(Bscore > Ascore)
     {
      iter->score += 3;
      iter->wincounter++;
     }
     else if(Ascore == Bscore)
     {
      iter->score += 1;
      iter->drawcounter++;
     }
     else
      iter->losecounter++;
     iter->sibalgoal += Ascore;
     iter->manygoal += Bscore;
     iter->gamecounter++;
     iter->goaldiff += Bscore - Ascore;
    }
   }

  }
  sort(teams.rbegin(), teams.rend());
  cout << tonorname << endl;
  for(int i = 0; i<teams.size(); i++)
  {
   printf("%d) %s %dp, %dg (%d-%d-%d), %dgd (%d-%d)\n", 
    i+1,
    teams[i].teamname.c_str(),
    teams[i].score,
    teams[i].gamecounter, 
    teams[i].wincounter,
    teams[i].drawcounter,
    teams[i].losecounter,
    teams[i].goaldiff,
    teams[i].manygoal,
    teams[i].sibalgoal);
  }
  if(n != N)
   cout << endl;
 }
 return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <limits>
#include <time.h>
#include <set>
using namespace std;


#ifdef mycom
#include <fstream>
ifstream fin("input");
#else
#define fin cin
#endif

vector<int> A;
vector<int> B;

 

 


int main()
{
 int testcase;

 testcase = 1;
 fin >> testcase;

 int hours;
 string solution; 
 solution.resize(10000);
 for(int i=1; i<=testcase; i++)
 {
  solution = "";

  hours = 0;
  int n;
  fin >> n;

  for(int j=1; j<=n; j++)
  {
   int temp;
   fin >> temp;
   A.push_back(temp);
  }

  sort(A.begin(), A.end());
  //saram 에 대한 처리가 들어감
  while(A.empty() == false)
  {
   if(A.size() == 1)
   {
    vector<int>::iterator b = A.begin();
    int _A = *b;

    B.insert(B.begin(), A.begin(), A.end());
    A.clear();

    char buf[256];
    sprintf(buf, "%d\n", _A);
    solution += buf;
    hours += _A;
   }
   else if(A.size() == 2)
   {
    vector<int>::iterator b = A.begin();
    int _A = *b;
    b++;
    int _B = *b;

    B.insert(B.begin(), A.begin(), A.end());
    A.clear();
    char buf[256];
    sprintf(buf, "%d %d\n", _A, _B);
    solution += buf;
    hours += _B;
   }
   else if(A.size() == 3)
   {
    vector<int>::iterator b = A.begin();
    int _A = *b;
    b++;
    int _B = *b;
    b++;
    int _C = *b;


    B.insert(B.begin(), A.begin(), A.end());
    A.clear();
    char buf[256];

    sprintf(buf, "%d %d\n", _A, _B);
    solution += buf;

    sprintf(buf, "%d\n", _A);
    solution += buf;

    sprintf(buf, "%d %d\n", _A, _C);
    solution += buf;
    hours += _A + _B + _C;
   }
   else if(A.size() >= 4)
   {
    vector<int>::iterator b = A.begin();
    vector<int>::reverse_iterator rb = A.rbegin();
    int _A = *b;
    b++;
    int _B = *b;
    int _Z = *rb;
    rb++;
    int _Y = *rb;

    A.erase(find(A.begin(), A.end(), _Y));
    A.erase(find(A.begin(), A.end(), _Z));
    //A.erase(_Y);
    //A.erase(_Z);
    B.push_back(_Y);
    B.push_back(_Z);
    if(_A + 2*_B + _Z <= 2*_A + _Y + _Z)
    {    
     char buf[256];
     sprintf(buf, "%d %d\n", _A, _B);
     solution += buf;
     sprintf(buf, "%d\n", _A);
     solution += buf;
     sprintf(buf, "%d %d\n", _Y, _Z);
     solution += buf;
     sprintf(buf, "%d\n", _B);
     solution += buf;

     hours += _A + 2*_B + _Z;
    }
    else
    {
     char buf[256];
     sprintf(buf, "%d %d\n", _A, _Z);
     solution += buf;
     sprintf(buf, "%d\n", _A);
     solution += buf;
     sprintf(buf, "%d %d\n", _A, _Y);
     solution += buf;
     sprintf(buf, "%d\n", _A);
     solution += buf;
     hours += 2*_A + _Y + _Z;
    }
   }
   sort(A.begin(), A.end());
   sort(B.begin(), B.end());
  }
  cout << hours <<endl << solution;
  if(testcase  != i)
   cout << endl;
 }

 return 0;
}

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <limits>
#include <time.h>
#include <set>
#include <cmath>
using namespace std;
//#define mycom
#ifdef mycom
#include <fstream>
ifstream fin("input");
#else
#define fin cin
#endif

using namespace std;
int main()
{
 int casenumber;
 fin >> casenumber;

 for(int i=1; i<=casenumber; i++)
 {
  int headnumber;
  fin >> headnumber;
  vector<int> s;
  for(int j=1; j<=headnumber; j++)
  {
   int temp;
   fin >> temp;
   s.push_back(temp);
  }
  
  int nmin = numeric_limits<int>::max();
  
  for(vector<int>::iterator iter = s.begin(); iter != s.end(); ++iter)
  {
   int sum = 0;
   for(vector<int>::iterator iter2 = s.begin(); iter2 != s.end(); ++iter2)
   {
    sum += abs(*iter - *iter2);
   }
   nmin = min(sum, nmin);
  }

  cout << nmin << endl;
 }
 return 0;
}