'COMPUTER TECH/C, C++'에 해당되는 글 34건

  1. 2010.08.12 의사결정 알고리즘.
  2. 2010.08.12 병합정렬
  3. 2010.08.12 암호!
  4. 2010.08.12 이진탐색트리-2
  5. 2010.08.12 이진탐색트리
  6. 2010.08.12 스마트 포인터란??
  7. 2010.08.12 이진탐색트리 erase 구현 방법!!
  8. 2010.08.12 이진탐색트리
  9. 2010.08.12 퀵 정렬
  10. 2010.08.12 힙 트리

< 의사 결정 알고리즘 >

*************************************************************************************

뇌세포, 곤충, 새, 자연현상 등을 통해서 알고리즘을 만든다.


복제 reproduction. - 부 모 의 염색체의 반반을 받아서 생성 (질서)

변이 : 부모의 염색체의 일부가 변이 (혼돈)


< 선택의 종류 >

*************************************************************************************

안정적 선택 = 복제. 안정성.

탐험적 선택 = 랜덤을 집어넣는다. 모험정신.

*************************************************************************************


추가자료 진화 알고리즘 검색해보기. 안티클론? 검색해보기. 셀룰러 검색해보기.

 

'COMPUTER TECH > C, C++' 카테고리의 다른 글

정렬을 하는 알고리즘의 예  (0) 2010.08.12
연결리스트  (0) 2010.08.12
의사결정 알고리즘.  (0) 2010.08.12
병합정렬  (0) 2010.08.12
암호!  (0) 2010.08.12
이진탐색트리-2  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요

2010. 8. 12. 23:44

< 병합정렬 >

*************************************************************************************

런 - 작업할 데이터의 집합 하나


3

15

28

31

2

6

8

9


#두 개의 런의 비교#


2 3 6 8 9 15 28 31 의 정렬이 가능.

 

 

 

 

 

 

 

 

 

 

 

 


위의 그림처럼 배열의 사이즈가 2보다 크다라면.. 계속 쪼개는 형식


위의 예)

*************************************************************************************

void Merge(Array, size, capacity)

{

 if(size>2)

 {

  Merge(Array, size/2, compare);

  Merge(Array+(size/2), size-size/2, compare);

 }

 Merge2(Array, size, compare);

}

위의 코드처럼 함수 작성 가능.

'COMPUTER TECH > C, C++' 카테고리의 다른 글

연결리스트  (0) 2010.08.12
의사결정 알고리즘.  (0) 2010.08.12
병합정렬  (0) 2010.08.12
암호!  (0) 2010.08.12
이진탐색트리-2  (0) 2010.08.12
이진탐색트리  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요

2010. 8. 12. 23:44

< 암호 >


< 대칭형 암호화 >

*************************************************************************************

F(원본, 키)

S(암호화된 데이터, 키)

암호화 할 때 사용한 키, 복구할 때 사용한 키가 동일한 경우를 말함.


ex) 암호화의 예

375 <-> 591

283 <-> 964

168 <-> 438

294 <-> 267

755 <-> 515

487 <-> 124

347 <-> 192

983 <-> 974

628 <-> 486

172 <-> 631

836 <-> 849

519 <-> (753)


뒷자리 x 3 한 값을 오른쪽 세 번째 자릿수에 쓴다.(이런식으로 사용)


자리바꿈, 패턴을 바꾸는 등 여러 가지를 통해서 해석하기 힘들게 만듬.


<영상압축>

그냥 통째로 저장할 경우 용량이 엄청나기 때문에 몇가지 방법을 사용함.


1. 기존에 기준 프레임을 주고 다음 장면엔 바뀐 부분만 신경씀.


2. 원본

0x12

0x78

0x99

0x68

0x54

0x12

0x10

0x76

0x18

0x54

0x12

0x9A

 

변화(1)

0x17

0x85

0xA2

0x15

0x71

0x1A

 

변화(2)

0x87

0x87

0xA7

0x77

0x57

0x27

0x17

0x77

0x17

0x57

0x17

0xA7


3. 그림파일 등 미디어를 저장할 때 187765(1이8개, 7이7개, 6이5개) 형식으로 저장


실질적으로 손실 압축을 함. 사람은 그렇게 대단하지 않기 때문에 손실을 해도 모름..

 

'COMPUTER TECH > C, C++' 카테고리의 다른 글

의사결정 알고리즘.  (0) 2010.08.12
병합정렬  (0) 2010.08.12
암호!  (0) 2010.08.12
이진탐색트리-2  (0) 2010.08.12
이진탐색트리  (0) 2010.08.12
스마트 포인터란??  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요

 < 이진탐색트리 >

*************************************************************************************

void Inorder(leaf * sr) <중위순회>

{

 if(sr) // sr이 한 개라도 있다면 (sr은 부모)

 {

  Inorder(sr->lc);

  print(sr);

  Inorder(sr->rc);

 }

}

<!>재귀함수를 이용.

재귀함수를 사용했을때 재귀함수를 사용하면 할수록 탈출조건에 가까워져야 함.

*************************************************************************************

< 이진탐색트리 삭제시 >

부모노드가 자식노드보다 먼저 소멸하면 안된다.

*************************************************************************************

< 소멸 예 >

void Postorder(leaf * sr) // 전부 소멸화 하는 예.

{

 if(sr)

 {

  Postorder(sr->lc);

  Postorder(sr->rc);

  Kill(sr);

 }

}


*************************************************************************************

< 파일에 저장했다가 로딩할 경우 >

3

5

7

10

13

17

20

25

27

30

35

36

37

40


* 위의 표 대로 보관해서 바로 사용하게 된다면 편향트리가 되버림.


하지만 재귀적인 방법으로 중위순회방법을 사용하여 불러올 경우 좀 더 균형이 잡혀있는 트리의 형태를 얻어올 수 있다.<형태를 똑같이 유지하지 않아도 될 시에>

*************************************************************************************

< 2번째 방법 >

왼쪽부터 차례대로 저장

20

10

5

3

7

13

17

30

25

27

40

35

37

36


이런식으로 저장하게 된다면 똑같은 형태의 트리의 구조를 얻어올 수 있다.

*************************************************************************************

< 루트를 중심으로 양쪽에 있는 노드를 전부 좌 우로 바꿀 경우 >

void SwapAll(leaf *sr)

{

 if(sr)

 {

  SwapAll(sr->lc);

  SwapAll(sr->rc);

  Swap(sr);

 }

}


void Swap(leaf * le)

{

 leaf *temp;

 temp = le->lc;

 re->lc = le->rc;

 le->rc = temp;

}

*************************************************************************************

<리스트를 이용한 트리>

class Tree

{

 class Leaf

 {

  T nd;

  Leaf * lc;

  Leaf * rc;

  Leaf * pa; // 방향성은 하향. 상향은 거론하지 않는다.

  Leaf * af;//after (리스트)

  Leaf * be;//before (리스트)

 }

}

*************************************************************************************

 


'COMPUTER TECH > C, C++' 카테고리의 다른 글

병합정렬  (0) 2010.08.12
암호!  (0) 2010.08.12
이진탐색트리-2  (0) 2010.08.12
이진탐색트리  (0) 2010.08.12
스마트 포인터란??  (0) 2010.08.12
이진탐색트리 erase 구현 방법!!  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요


< binary search coding >

*************************************************************************************

< 생성자 >

template <class T, class K, class F>(타입, key타입, 함수 객체<비교논리> 사용)

*************************************************************************************

void insert(Pair<T.K>in)

{

 EhNode * pa;

 pa = 집어넣을 위치를 찾는다(in);


 pa 의 키와 in의 키가 같다면 함수종료

 

 EhNode * node = new EhNode(in);

 매달기(now, pa);

}

'COMPUTER TECH > C, C++' 카테고리의 다른 글

암호!  (0) 2010.08.12
이진탐색트리-2  (0) 2010.08.12
이진탐색트리  (0) 2010.08.12
스마트 포인터란??  (0) 2010.08.12
이진탐색트리 erase 구현 방법!!  (0) 2010.08.12
이진탐색트리  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요


< 스마트 포인터 > = 포인터는 아닌데 포인터의 역할을 한다

*************************************************************************************

class Stu

{

 int refcnt;

 class RealStu

 {

  const int num;

 public:

  RealStu(int _num) : num(_num)

  {

   refcnt++;

  }

  void Attach()

  {

   refcnt++;

  }

 }

 int refcnt;

 RealStu * stu;

public:

 Stu(int _num)

 {

  stu = new RealStu(_num);

 }

 Stu(const RealStu &rstu)

 {

  stu = stu.rstu;

  Stu.Attach();

 }

};


void Foo()

{

 Stu s(2);

 zoo(5);

}

void zoo(stu s2)

{

 s2.study();

}

스마트 포인터의 소멸에 대한 부분은 책임지고 잘 구현해야 함.

*************************************************************************************

< Stu 의 소멸자 >

virtual ~Stu()

{

 if(!rstu.Detach())

 {

  delete rstu;

 }

}

*************************************************************************************

< RealStu 안에 정의 되어야 할 함수 >

bool Detach()

{

 refcnt--;

 return refcnt!=0;

}

*************************************************************************************

 

우리는 Stu 를 통해서 모든것을 처리하지만 Stu 는 껍데기일 뿐이다!!

 

속안에 있는 RealStu 라는 클래스가 진짜 이용되는 클래스이다.

 

위의 코딩방법을 쓰면 값복사 대신에 원본 그대로의 데이터를 이용해서 작업을 처리 할 수 있다.

 

나중에 유용하게 쓰일 상식인것 같다.

'COMPUTER TECH > C, C++' 카테고리의 다른 글

이진탐색트리-2  (0) 2010.08.12
이진탐색트리  (0) 2010.08.12
스마트 포인터란??  (0) 2010.08.12
이진탐색트리 erase 구현 방법!!  (0) 2010.08.12
이진탐색트리  (0) 2010.08.12
퀵 정렬  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요

void DeltempNode(EhNode *now)

{

 parent = now->pa

 child = ld or rd 를 선언.

 if (자식 둘)

 {

  now = ChangeMe(now); // 대체값을 찾아서 대체할 놈을 반환.

 }


 (else 가 아니다!!)

 부모 = now‘s 부모

 

 if(자식 = now's 왼쪽자식) || (자식=now's 오른 자식);

 

 if(부모가 없다면)

  root = 자식;

 else

 {

  if(now가 부모의 왼쪽 자식이라면)

  {

   부모의 왼쪽 = 자식

  }

  else(오른쪽이라면)

  {

   부모의 오른 = 자식

  }

 }


 if(자식이 있다면)

 {

  자식의 부모 = 부모

 }

 now 는 죽음.

}


'COMPUTER TECH > C, C++' 카테고리의 다른 글

이진탐색트리  (0) 2010.08.12
스마트 포인터란??  (0) 2010.08.12
이진탐색트리 erase 구현 방법!!  (0) 2010.08.12
이진탐색트리  (0) 2010.08.12
퀵 정렬  (0) 2010.08.12
힙 트리  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요


< 이진탐색트리 >

*************************************************************************************

void Inorder(leaf * sr) <중위순회>

{

 if(sr) // sr이 한 개라도 있다면 (sr은 부모)

 {

  Inorder(sr->lc);

  print(sr);

  Inorder(sr->rc);

 }

}

<!>재귀함수를 이용.

재귀함수를 사용했을때 재귀함수를 사용하면 할수록 탈출조건에 가까워져야 함.

*************************************************************************************

< 이진탐색트리 삭제시 >

부모노드가 자식노드보다 먼저 소멸하면 안된다.

*************************************************************************************

< 소멸 예 >

void Postorder(leaf * sr) // 전부 소멸화 하는 예.

{

 if(sr)

 {

  Postorder(sr->lc);

  Postorder(sr->rc);

  Kill(sr);

 }

}


*************************************************************************************

< 파일에 저장했다가 로딩할 경우 >

3

5

7

10

13

17

20

25

27

30

35

36

37

40


* 위의 표 대로 보관해서 바로 사용하게 된다면 편향트리가 되버림.


하지만 재귀적인 방법으로 중위순회방법을 사용하여 불러올 경우 좀 더 균형이 잡혀있는 트리의 형태를 얻어올 수 있다.<형태를 똑같이 유지하지 않아도 될 시에>

*************************************************************************************

< 2번째 방법 >

왼쪽부터 차례대로 저장

20

10

5

3

7

13

17

30

25

27

40

35

37

36


이런식으로 저장하게 된다면 똑같은 형태의 트리의 구조를 얻어올 수 있다.

*************************************************************************************

< 루트를 중심으로 양쪽에 있는 노드를 전부 좌 우로 바꿀 경우 >

void SwapAll(leaf *sr)

{

 if(sr)

 {

  SwapAll(sr->lc);

  SwapAll(sr->rc);

  Swap(sr);

 }

}



void Swap(leaf * le)

{

 leaf *temp;

 temp = le->lc;

 re->lc = le->rc;

 le->rc = temp;

}

*************************************************************************************

<리스트를 이용한 트리>

class Tree

{

 class Leaf

 {

  T nd;

  Leaf * lc;

  Leaf * rc;

  Leaf * pa; // 방향성은 하향. 상향은 거론하지 않는다.

  Leaf * af;//after (리스트)

  Leaf * be;//before (리스트)

 }

}

*************************************************************************************

'COMPUTER TECH > C, C++' 카테고리의 다른 글

스마트 포인터란??  (0) 2010.08.12
이진탐색트리 erase 구현 방법!!  (0) 2010.08.12
이진탐색트리  (0) 2010.08.12
퀵 정렬  (0) 2010.08.12
힙 트리  (0) 2010.08.12
피보나치 수열  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요

2010. 8. 12. 23:41

< 퀵 정렬 >

*************************************************************************************

20

13

2

75

10

5

13

12

9

15

23

17


맨 뒤를 피벗이라고 생각


피벗보다 작은것은 왼쪽으로, 피벗보다 큰것은 오른쪽으로.

*************************************************************************************

퀵 소트 수행과정을 T(n)이라 하고, 피벗을 중심으로 할때 T'(n)이라 할때,


T'(n) = n (비교 n번) , 최악의 경우는 n+n 번이 될 수도 있음.


T(n) = T'(n) + T(n/2) + T(n/2)

     = T'(n) + 2*T(n/2)

     = T'(n) + 2*(T'(n/2)+2*T(n/22))

     = T'(n) + 2*T'(n/2) + 22 * T(n/22))

     = T'(n) + 2*T'(n/2)+22 * (T'(n/22)+2*T(n/23))

     = T'(n) + 2*T'(n/2) + 22 * T(n/22) + ... + 2h * T'(n/2h)

    = 2n + 2 * (2*n/22) + 22(2*n/22) + ... 2n

    = 2n + 2n + 2n + ... 2n

    = 2hn = 2nlog2n

    = h = log2n

*************************************************************************************


< 퀵 소트의 최악의 경우 >

1

2

3

4

5

6

7

8

9

10


이런 경우는 n2번이 나온다.

'COMPUTER TECH > C, C++' 카테고리의 다른 글

이진탐색트리 erase 구현 방법!!  (0) 2010.08.12
이진탐색트리  (0) 2010.08.12
퀵 정렬  (0) 2010.08.12
힙 트리  (0) 2010.08.12
피보나치 수열  (0) 2010.08.12
MyVector만들기  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요

2010. 8. 12. 23:40

< 힙 트리 >

*************************************************************************************

부모가 자식보다 열등 or 우등


부모가 가지고 있는 키가 자식이 가지고있는 킷값보다 커야한다.


힙의 종류


Up Heap(MAX Heap) 가장 큰 수를 아래서부터 위로


Down Heap가장 작은수를 루트로 넣고 비교해서 자리를 찾는 방법


int GetPa(int me)

{

 return (me-1)/2 // 부모 구하는 방법

}


int GetLc(int me)

{

 return 2*me+1; // 자식 구하는 방법 (Lc)

}

*************************************************************************************

< 힙의 최악의 경우 >


10

15

2

7

8

6

4

(높이)

0

1

1

2

2

2

2


20 * 0 + 21 * 22 * 2 + ... + 2h * h

 <= 2h * h + 2h * h + ... + 2h * h

  = h2 * 2h = (logn)2 * 2log2n = n*(logn)2

'COMPUTER TECH > C, C++' 카테고리의 다른 글

이진탐색트리  (0) 2010.08.12
퀵 정렬  (0) 2010.08.12
힙 트리  (0) 2010.08.12
피보나치 수열  (0) 2010.08.12
MyVector만들기  (0) 2010.08.12
최단경로 알고리즘  (0) 2010.08.09
Posted by ... XJAPAN

댓글을 달아 주세요

이전버튼 1 2 3 4 이전버튼