전체보기 (305) 썸네일형 리스트형 [Algorith] 삽입 정렬 (Insertion Sort) 정렬 전 3 7 9 1 2 1차 정렬 3 7 9 1 2 2차 정렬 3 7 9 1 2 3차 정렬 1 3 7 9 2 4차 정렬 1 2 3 7 9 비교 횟수는 데이터 수와 같다. 최악의 경우엔 N(N-1)/2 의 계산이 필요하다. 또한 데이터의 이동 횟수도 N(N-1)/2의 계산이 나온다 따라서 정렬이 잘된 리스트를 가지고 삽입 정렬을 하면 선택 정렬에 비해 빠를 수 있다. 왜냐면 삽입 정렬의 비교가 비교적 선택 정렬보다 적을 수 있기 때문이다. 그래서 정렬이 잘 되어 있다면 O(N)에 가까운 계산이 나올 수 있다. 다만 정렬이 안된 상태라면 선택 정렬이 빠를 수 있다. Big-O 표기법의 의한 O(N^2)이다. #include #include #define MAX 100 #define TRUE 1 #defi.. [Algorith] 선택 정렬 (Selection sort) 정렬 전 3 7 9 1 2 1차 정렬 1 7 9 3 2 2차 정렬 1 2 9 3 7 3차 정렬 1 2 3 9 7 4차 정렬 1 2 3 7 9 정렬을 할때 위와 같이 첫 번째 원소의 값을 그 뒤의 나머지 원소들 중 가장 작은 값과 바꾼다. 두번째 원소의 값을 그 뒤의 원소들 가장 작은 값과 바꾼다. 위와 같이 반복하면 정렬이 끝난다. 선택 정렬은 비교 하는데 N^2/2회나 되지만 데이터 교환에는 N번의 횟수면 된다. 때문에 정렬 데이터가 큰 경우 다른 정렬 알고리즘에 비해 유용하다. Big-O 표기법의 의한 계산 O(N^2) (단순 계산으로는 for문이 중첩되는 경우므로 N*N=N^2이 나온다.) #include #include #define MAX 100 #define TRUE 1 #define FALS.. [Algorith] 이진 트리 (Tree) - 레벨 순회 (Level-Order Traverse) A -> B -> C -> D -> E -> F -> G 순서로 나온다. 레벨 순회는 스택보다 큐를 사용하는 것이 바람직 하다. /*------------------*/ /* main.c */ /*------------------*/ #include "Appendix.h" /* Definition of External Functions */ extern void InitializeQueue(void); extern void Put(NODE *); extern NODE *Get(void); extern int IsQueueEmpty(void); /* Definition of Internal Functions */ void InitializeTree(void); // 트리의 기본적인 헤드와 엔드 노드를 만는.. [Algorith] 이진 트리 (Tree) - 후위 순회 (Post-Oreder Traverse) /*------------------*/ /* main.c */ /*------------------*/ #include "Appendix.h" /* Definition of External Functions */ extern void InitializeStack(void); extern void Push(NODE *); extern NODE *Pop(void); extern int IsStackEmpty(void); /* Definition of Internal Functions */ void InitializeTree(void); // 트리의 기본적인 헤드와 엔드 노드를 만는다. void MakeTree(void); // 트리의 기본적으로 들어갈 데이터의 값을 만든다. void Traverse(NOD.. [Algorith] 이진 트리 (Tree) - 중위 순회 (In-Order Traverse) { D -> B -> E -> A -> F -> C -> G 순서로 이동한다. 전위 순회의 코드를 이용하여 Traverse() 함수만 바꿔주면 된다. /*------------------*/ /* main.c */ /*------------------*/ #include "Appendix.h" /* Definition of External Functions */ extern void InitializeStack(void); extern void Push(NODE *); extern NODE *Pop(void); extern int IsStackEmpty(void); /* Definition of Internal Functions */ void InitializeTree(void); // 트리의 기본적인 .. [Algorith] 이진 트리 (Tree) - 전위 순회 (Pre-Order Traverse) 나오는 순서는 위 그림과 같이 A -> B -> D -> E -> C -> F -> G 순서이다. /*------------------*/ /* main.c */ /*------------------*/ #include "Appendix.h" /* Definition of External Functions */ extern void InitializeStack(void); extern void Push(NODE *); extern NODE *Pop(void); extern int IsStackEmpty(void); /* Definition of Internal Functions */ void InitializeTree(void); // 트리의 기본적인 헤드와 엔드 노드를 만는다. void MakeTree.. [Data Struct] 큐 (Queue) - 링크드 리스트를 이용한 큐 #include #include typedef struct _NODE // 새로운 타입 선언 { int Data; struct _NODE *Next; } NODE; NODE *Front, *Rear; // Front = Get()함수를 쓸때 데이터 가져오기, Rear은 Put() 함수를 쓸때 데이터 저장하기 위해 사용 NODE *ptrNode; void InitializeQueue(void); void Put(int); void DisplayQueue(void); int Get(void); void main() { int ret; InitializeQueue(); printf("Put() 함수를 호출해 보죠!\n"); Put(1); Put(3); Put(10); Put(20); Put(12); print.. [Data Struct] 스택 (Queue) - 배열을 이용한 스택 Put() - 자료를 넣는 함수 Get() - 자료를 빼는 함수 #include #define MAX 100 /* Queue 선언 */ int Queue[MAX]; int Front, Rear; void InitializeQueue(void); // 큐 초기화 함수 void Put(int); // 데이터의 삽입 void DisplayQueue(void); // 큐를 보여줌 int Get(void); // 데이터의 꺼냄 void main() { int ret; InitializeQueue(); Put(1); Put(3); Put(10); Put(20); Put(12); printf("\n다섯 번의 Put() 호출 후 결과 \n"); DisplayQueue(); ret = Get(); ret = Get();.. 이전 1 ··· 29 30 31 32 33 34 35 ··· 39 다음
