'yong's'에 해당되는 글 154건

  1. 2009.12.17 병합정렬 & 퀵 정렬 비교 및 기수정렬
  2. 2009.12.16 연결리스트더미有
  3. 2009.12.16 퀵 정렬
  4. 2009.11.20 템플릿이란!?


병합 정렬

1. 분할!! 정렬이 안된 배열을 쪼갠다 [ 7, 5, 12, 18, 4, 9, 11] - 최소원소들이 될때까지 계속 병합정렬 호출

2. 병합!! 최소원소들을 합쳐가면서 병합시킨다.


퀵 정렬과 비교!

퀵 - 역순 , 적당히 정렬에서는 느리고 굉장히 어지러운 정렬에서는 효과를 발휘한다. 일반적으로 빠른 소트로 알려져있다.
     컴퓨터상에서는 평균보다 최악의 상황이 더 중요하다.

병합 - 실질적으로 빠른 정렬 ,  단점 : 메모리 사용량 ↑




count 정렬 

1

2

3

4

1

3

1

정렬전!


 

1

2

3

4

3개

1개

2개

1개

cnt =3

cnt =4

cnt =6

cnt =7

분석법을 이용해 표 작성

 

1

2

3

4

1

3

1

 

 

 

 

 

 

4

cnt--

1

2

3

4

1

3

1

 

 

 

 

 

3

4

cnt--
 

1

2

3

4

1

3

1

 

 

 

 

3

3

4

 cnt--

1

2

3

4

1

3

1

 

 

 

2

3

3

4

cnt--

1

2

3

4

1

3

1

 

 

1

2

3

3

4

cnt--

1

2

3

4

1

3

1

 

1

1

2

3

3

4

cnt--

1

2

3

4

1

3

1

1

1

1

2

3

3

4

cnt--

cnt==0 이 되고 정렬 끝  1 , 1, 1 ,2 ,3 ,3, 4




count
 카운트 소트를 이용한 radix sort(기수정렬)

121     121    121    121
753     753    753    275
275     473    473    473
473     275    275    753
      첫자리 두번째 세번째

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

지뢰찾기  (0) 2010.05.03
3n+1  (0) 2010.05.03
스케줄링 (라운드 로빈)  (0) 2009.12.17
연결리스트더미有  (0) 2009.12.16
퀵 정렬  (0) 2009.12.16
Posted by 아몰라

연결리스트


노드 - 데이터를 보관해준다!

head - 맨앞의 노드를 지칭
tail - 맨뒤의 노드를 지칭
head랑 tail은 위치정보만 가지고있다.(링크다!)

단일연결 - 어떠한 노드의 위치를 알수없다. (Stoker)
이중연결 - 어떠한 노드의 위치를 알수있다.


seek를 이용 seek<노드의값 이면 앞에 삽입하자!

Dummy 노드 있는게 더 좋다. 특정한 노드 사이에 저장이된다!


pushback - 맨 뒤에 보관한다.

1. in을 보관하는 노드 생성
2. tail 앞에 보관



Ehlist()                               //헤드랑 테일 초기화~
  {
   head = new EhNode();       //시작을 가르킬더미 생성
   tail = new EhNode();          //마지막을 가르킬 더미 생성
   head->af = tail;                
   tail->be = head;
   usage = 0;                      // 연결리스트의 개수를 알려준다
   
  }
  virtual ~Ehlist()
  {
   EhNode * ehnode = tail->be;  // 테일이 가르키는 노드의 옆에노드를 가르킨다.

   while(usage!=0)
   {
    tail->be = tail->be->be;       // 테일을 왼쪽왼쪽 가르키게 한다. 
    delete tail->be;                  // 테일 옆에 노드를 삭제
    usage--;
    
   }

   delete tail,head;
  }

  
  void push_back(T data)
  {
   EhNode * ehnode;
   ehnode = new EhNode(data);
   HangNode(ehnode, end().now); //노드를 넣을 데이터와 마지막 노드의 위치를 넘겨준다.
   usage++;

  }
  
  void insert(iterator at,T data)
  {
   EhNode * ehnode;
   ehnode = new EhNode(data);
   HangNode(ehnode, at.now);  //노드를 넣을 데이터와 선택위치를 넘겨준다.
   usage++;
  }

  
  void erase(iterator at)
  {
   EhNode * ehnode = at.now;
   ehnode->be->af = ehnode->af;
   ehnode->af->be = ehnode->be;
   usage--;
  }

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

지뢰찾기  (0) 2010.05.03
3n+1  (0) 2010.05.03
스케줄링 (라운드 로빈)  (0) 2009.12.17
병합정렬 & 퀵 정렬 비교 및 기수정렬  (0) 2009.12.17
퀵 정렬  (0) 2009.12.16
Posted by 아몰라


퀵 정렬

1. pivot을 선택한다.

2. pivot을 맨 앞(L)뒤(R)의 요소와 교환

3. pivot 보다 (L)에서 큰원소들을 찾는다.

4. pivot 보다 (R)에서 작은원소들을 찾는다.

5. 3~4에서 둘다 값을 찾으면 서로 값 교환한다.

6. L 과 R 이 만나게되면 pivot과 만나는 점을 교환하고 pivot을 확정한다.

7. pivot 왼쪽 quick sort - 원소 개수가 2개이상

   pivot 오른쪽 quick sort - 원소 개수가 2개이상

8. pivot이 다 확정되면 종료

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

지뢰찾기  (0) 2010.05.03
3n+1  (0) 2010.05.03
스케줄링 (라운드 로빈)  (0) 2009.12.17
병합정렬 & 퀵 정렬 비교 및 기수정렬  (0) 2009.12.17
연결리스트더미有  (0) 2009.12.16
Posted by 아몰라

//템플릿이란!!?? 함수를 템플릿화하면 자료형은 결정되지않는다! 자료형을 자유롭게!!!

////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
using::std::endl;
using::std::cout;

template <typename T>   //템플릿은 모형자!

T Add(T a, T b)
{
 return a+b;
}

int main(void)
{
 cout<<Add(10,20)<<endl;  //한번 모형자로 펜을 잡고(함수를 시작한다) 도형을 그리기 시작하면 펜을 놓기전(함수종료)에는 다른 펜을 사용할수없다
 cout<<Add(1.1,2.2)<<endl; //펜을 바꾼다 ( 자료형을 바꾼다 )
 return 0;
}

*/


///////////////////////////////////////////////////////////////////////////////////////


//함수 템플릿!!

// "함수 템플릿" 이라고 부른다는 것은 템플릿임을 강조하는 것이다.(함수가 아니라는 뜻이 아니다).
// 함수이기 전에 템플릿의 정의해 해당된다는 것을 의미한다.

 


template <typename T1, typename T2> //이것은 한 함수에 펜을 2개 사용할수 있게 해준다!

void ShowData(T1 a, T2 b) 
{
 cout<<a<<endl;
 cout<<b<<endl;
}

int main(void)
{
 ShowData(1, 2);
 ShowData(3, 2.5);
 return 0;
}


////////////////////////////////////////////////////////////////////////////////////

//함수 템플릿 특수화 선언

 

#include <iostream>
using::std::endl;
using::std::cout;

template <typename T> //함수 템플릿 정의
int SizeOf(T a)
{
 return sizeof(a);
}
/*
                   다음과 같이 한 줄에 표현하는 것이 보통이다.

template<>    //함수 템플릿 특수화 선언       선언1:template<> int SizeOf(char *a)
                   선언2:template<> int SizeOf<>(char *a)
int SizeOf(char *a)  //전달 인자가 char *인 경우에는 이 함수를 호출  선언3:template<> int SizeOf<char*>(char *a)
{                   선언3의 형태가 가장 정확한 표현이고, 선언1과 2는 선언3을 줄여서 표현한
 return strlen(a);              형태이다. 그러므로 선언 3의 표현 방법도 기억하자!!!
}

*/
int main(void)
{
 int i=10;
 double e=7.7;
 char * str= "Good Morning!";

 cout<<SizeOf(i)<<endl;
 cout<<SizeOf(e)<<endl;
 cout<<SizeOf(str)<<endl;
 
 return 0;
}


////////////////////////////////////////////////////////////////////////////////////

 


template <typename T>
class Data      //클래스 템플릿도 선언과 정의를 분리하는 것이 가능하다.
{
 T data;

 public:

  Data(T d);
  void SetData(T d);
  T GetData();
};

template <typename T>
Data<T>::Data(T d)
{
 data = d;
}

template <typename T>
void Data<T>::SetData(T d) // Data<T> 이것은 T타입에 대해서 템플릿으로 정의되어 있는 "Data
{       // 클래스 템플릿"을 의미

       // Data::SetData 는 Data클래스의 멤버 함수를 정의하는 것이지
 data = d;    // "Data 클래스 템플릿"의 멤버 함수를 정의하는 것이 아니다.
}

template <typename T>
T Data<T>::GetData()
{
 return data;
}


////////////////////////////////////////////////////////////////////////////////////////


//스택 클래스의 템플릿화!!


template <typename T>
class Stack{
 private:
  int topidx;   // 마지막 입력된 위치의 인덱스
  T *stackPtr;  // 스택 포인터

 public:
  Stack(int s=10);
  ~Stack();
  void Push(const T& pushValue);
  T Pop();
};

template <typename T>
Stack<T>::Stack(int len)
{
 topIdx=-1;    // 스택 인덱스 초기화
 stackPtr=new T[len];
}

template <typename T>
Stack<T>::~Stack()
{
 delete[] stackPtr;
}

template <typename T>
void Stack<T>::Push(const T& pushValue)  // 스택에 데이터 입력
{
 stackPtr[++topIdx]=pushValue;
}

template <typename T>
T Stack<T>::Pop()    //스택에서 꺼냄
{
 return stackPtr[topIdx--];
}


int main()
{
 Stack<char> stack1(10);     // char형 데이터를 저장하기 위한 stack 객체를 생성!
 stack1.Push('A');
 stack2.Push('B');
 stack3.Push('C');

 for(int i=0; i<3; i++)
 {
  cout<<stack1.Pop()<<endl;
 }

 Stack<int> stack2(10);     // int형 데이터 저장을 위한 stack 객체를 생성!
 stack2.Push(10);
 stack2.Push(20);
 stack2.Push(30);

 for(int j=0; j<3; j++)
 {
  cout<<stack2.Pop()<<endl;
 }

 return 0;
}

// stack 클래스 처럼 템플릿화하면 , 하나의 자료형에 종속되지 않는다!
// 이런식으로 자주 사용되는 자료 구조와 알고림을 템플릿으로 정의해 놓으면, 여러모로 유용할 것이다!

 


///////////////////////////////////////////////////////////////////////////////////////////////////

//템플릿 함수 or 템플릿 클래스!!!


template <typename T>  //함수 템플릿 정의!
T Add(T a, T b)
{
 return a+b;
}

 

int main(void)
{
 cout<<Add(10,20)<<endl;    // 함수 템플릿의 T가 int로 해석되어서 호출되기를 바라고있다. 그러나 실제로는 컴파일러가 int형 함수를만든다. 그것을 호출한다.
 cout<<Add(1.1,2.2)<<endl;   // 위와 동일하고 Double형 함수를 만든다!
 cout<<Add(10,20)<<endl;    // 첫번째줄에서 만든 함수를 호출해온다!
 return 0;     

 // 이처럼 함수 템플릿을 기반으로 해서 만들어지는, 실제 호출이 가능한 함수들을 가리켜 템플릿 함수라고 부른다!
 // 또한 템플릿 함수가 생성되는 현상을 가리켜서 "함수 템플릿의 인스턴스화"라고 부른다!
}

'프로그래밍 기초 > C++' 카테고리의 다른 글

반올림함수 만들기  (0) 2010.05.11
가상함수테이블  (0) 2010.03.04
다형성  (0) 2010.03.04
This 포인터  (0) 2010.01.24
Posted by 아몰라